C. Protocols and .. , 16 2.1.2.2 The Medium Access Control Layer

T. Knapsack, P. Multiprocessor, and M. , 23 2.3.1 Exact Algorithms for 24 2.3.2 Heuristic Algorithms for The HEU, M-HEU, I-HEU and MVRC Algorithms, and CCP Algorithms . . . . . . . . . . . . . 27 2.3.2.5 The Der Algo, RLS, MRLS and Other Variations

D. Algorithms and .. , 38 3.4.1 Brute force algorithm, p.41

A. Mnu and M. , 56 4.3.1 An exact algorithm for, p.62

A. Adapted-to-the-zigbee-network and .. , 79 5.2.1 Traffic estimation with the ZigBee tree, p.79

P. Evaluation and .. , 81 5.3.2 Simulation setup, Control message overhead, p.84

M. [. Alam, M. Hasan, A. S. Hossain, and . Sohail, Heuristic solution of MMKP in different distributed admission control and QoS adaptation architectures for video on demand service, 2nd International Conference on Broadband Networks, 2005., pp.896-903, 2005.
DOI : 10.1109/ICBN.2005.1589700

M. M. Akbar, E. G. Manning, G. C. Shoja, and S. Khan, Heuristic Solutions for the Multiple-Choice Multi-dimension Knapsack Problem, ICCS '01: Proceedings of the International Conference on Computational Science-Part II, pp.659-668, 2001.
DOI : 10.1007/3-540-45718-6_71

M. Rahman, M. Kaykobad, E. G. Manning, and G. C. Shoja, Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls, Comput. Oper. Res, vol.33, issue.5, pp.1259-1273, 2006.

B. Mani, C. Strivastava-andreas-savvides, and . Han, Dynamic fine-grained localization in ad-hoc networks of sensors, ACM Mobicom, 2001.

J. Burrell, T. Brooke, and R. Beckwith, Vineyard computing: sensor networks in agricultural production. Pervasive Computing, IEEE, vol.3, issue.1, pp.38-45, 2004.

J. Boudec, Rate adaptation, congestion control and fairness: a tutorial, 2006.

M. Chantzara and M. E. Anagnostou, MVRC Heuristic for Solving the Multi-Choice Multi-Constraint Knapsack Problem, International Conference on Computational Science, pp.579-587, 2006.
DOI : 10.1007/11758501_78

D. Culler, D. Estrin, and M. Srivastava, Guest Editors' Introduction: Overview of Sensor Networks, Computer, vol.37, issue.8, pp.41-49, 2004.
DOI : 10.1109/MC.2004.93

[. Chen, Lexicographic Maxmin Fairness for Data Collection in Wireless Sensor Networks, IEEE Transactions on Mobile Computing, vol.6, issue.7, pp.762-776, 2007.
DOI : 10.1109/TMC.2007.1039

N. Cherfi and M. Hifi, A column generation method for the multiplechoice multi-dimensional knapsack problem, Comput. Optim. App. online first, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00308694

J. Chen and X. Koutsoukos, Survey on coverage problems in wireless ad hoc sensor networks, the IEEE SouthEastCon Conf, 2007.

C. Chen and J. Ma, Mobile enabled large scale wireless sensor networks, International Conference on Advanced Communication Technology (ICACT), 2006.

[. Cardei and J. Wu, Handbook of Sensor Networks, 2004.

M. E. Dyer and J. Walker, Dominance in multi-dimensional multiplechoice knapsack problems, Asia-Pacific Journal of Operational Research, vol.15, issue.2, pp.159-168, 1998.

R. Cheng-tien-ee and . Bajcsy, Congestion control and fairness for many-to-one routing in sensor networks, SenSys '04: Proceedings of the 2nd international conference on Embedded networked sensor systems, pp.148-161, 2004.

P. C. Gilmore and R. E. Gomory, A Linear Programming Approach to the Cutting-Stock Problem, Operations Research, vol.9, issue.6, pp.849-859, 1961.
DOI : 10.1287/opre.9.6.849

P. C. Gilmore and R. E. Gomory, A Linear Programming Approach to the Cutting Stock Problem???Part II, Operations Research, vol.11, issue.6, pp.863-888, 1963.
DOI : 10.1287/opre.11.6.863

P. Gupta and P. R. Kumar, The capacity of wireless networks, IEEE Transactions on Information Theory, vol.46, issue.2, pp.388-404, 2000.
DOI : 10.1109/18.825799

Y. Ganjali and A. Keshavarzian, Load balancing in ad hoc networks: single-path routing vs. multi-path routing, IEEE INFOCOM 2004, 2004.
DOI : 10.1109/INFCOM.2004.1356998

S. Chaitr and . Hiremath, New Heuristic And Metaheuristic Approaches Applied To The Multiple-choice Multidimensional Knapsack Problem, 2008.

B. Hull, K. Jamieson, and H. Balakrishnan, Mitigating congestion in wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems , SenSys '04, pp.134-147, 2004.
DOI : 10.1145/1031495.1031512

B. Han, J. Leblet, and G. Simon, Query range problem in wireless sensor networks, IEEE Communications Letters, vol.13, issue.1, pp.55-57, 2009.
DOI : 10.1109/LCOMM.2009.081546

A. Cornelis, M. De-kluyver-harvey, and . Salkin, The knapsack problem: A survey, Naval Research Logistics Quarterly, vol.22, issue.1, pp.127-144, 1975.

M. Hifi, M. Michrafy, and A. Sbihi, Heuristic algorithms for the multiple-choice multidimensional knapsack problem, Journal of the Operational Research Society, vol.15, issue.12, pp.1323-1332, 2004.
DOI : 10.1287/ijoc.15.3.267.16080
URL : https://hal.archives-ouvertes.fr/hal-00125572

M. Hifi, M. Michrafy, and A. Sbihi, A Reactive Local Search-Based Algorithm for the Multiple-Choice Multi-Dimensional Knapsack Problem, Computational Optimization and Applications, vol.21, issue.3, pp.271-285, 2006.
DOI : 10.1007/s10589-005-3057-0
URL : https://hal.archives-ouvertes.fr/hal-00125573

B. Han and G. Simon, Fair Capacity Sharing Among Multiple Sinks in Wireless Sensor Networks, 2007 IEEE Internatonal Conference on Mobile Adhoc and Sensor Systems, pp.1-9, 2007.
DOI : 10.1109/MOBHOC.2007.4428641

R. Jain, D. Chiu, and W. Hawe, A quantitative measure of fairness and discrimination for resource allocation in shared computer systems, 1998.

F. Kelly, Charging and rate control for elastic traffic, European Transactions on Telecommunications, vol.13, issue.1, pp.33-37, 1997.
DOI : 10.1002/ett.4460080106
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.144.6615

S. Khan, Quality Adaptation in a Multisession Multimedia System: Model, Algorithms and Architecture, 1998.

[. Khan, K. F. Li, E. G. Manning, and M. , Mostofa Akbar. Solving the knapsack problem for adaptive multimedia systems, Stud. Inform. Univ, vol.2, issue.1, pp.157-178, 2002.

F. Kelly, A. Maulloo, and D. Tan, Rate control in communication networks: shadow prices, proportional fairness and stability, 1998.

C. Y. Lee and H. K. Cho, Discrete bandwidth allocation considering fairness and transmission load in multicast networks, Computers & Operations Research, vol.34, issue.3, pp.884-899, 2007.
DOI : 10.1016/j.cor.2005.05.016

[. Levis, TEP 111: message t

J. Luo and J. Hubaux, Joint mobility and routing for lifetime elongation in wireless sensor networks, IEEE INFOCOM, 2005.

[. Lee and J. Lehoczky, Ragunathan (Raj) Rajkumar, and Dan Siewiorek. On quality of service optimization with discrete qos options, RTAS'99: Proceedings of the Fifth IEEE Real-Time Technology and Applications Symposium, p.276, 1999.

C. Y. Lee, Y. P. Moon, and Y. Cho, A lexicographically fair allocation of discrete bandwidth for multirate multicast traffics, Computers & Operations Research, vol.31, issue.14, pp.312349-2363, 2004.
DOI : 10.1016/S0305-0548(03)00191-6

]. Lorincz, D. J. Malan, T. R. Fulford-jones, A. Nawoj, A. Clavel et al., Sensor Networks for Emergency Response: Challenges and Opportunities, IEEE Pervasive Computing, vol.3, issue.4, pp.16-23, 2004.
DOI : 10.1109/MPRV.2004.18

M. Li and B. Yang, A survey on topology issues in wireless sensor networks, the 2006 International Conf. on Wireless Networks (ICWN), 2006.

R. Muller and G. Alonso, Efficient Sharing of Sensor Networks, 2006 IEEE International Conference on Mobile Ad Hoc and Sensor Sysetems, 2006.
DOI : 10.1109/MOBHOC.2006.278547

[. Marco, E. J. Duarte-melo, M. Liu, and D. L. Neuhoff, On the Many-to-One Transport Capacity of a Dense Wireless Sensor Network and the Compressibility of Its Data, IEEE/ACM IPSN, 2003.
DOI : 10.1007/3-540-36978-3_1

G. Mao, B. Fidan, and B. D. Anderson, Wireless sensor network localization techniques, Computer Networks, vol.51, issue.10, pp.2529-2553, 2007.
DOI : 10.1016/j.comnet.2006.11.018

M. Moser, P. Dusan, N. Jokanovi´cjokanovi´c, and . Shiratori, An algorithm for the multidimensional multiple-choice knapsack problem. IEICE transactions on fundamentals of electronics, communications and computer sciences, pp.582-589, 1997.

M. Moser, Declarative scheduling for optimally graceful QoS degradation, Proceedings of the Third IEEE International Conference on Multimedia Computing and Systems, p.86, 1996.
DOI : 10.1109/MMCS.1996.534959

S. Martello and P. Toth, Knapsack problems: algorithms and computer implementations, 1990.

J. Mo and J. Walrand, Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking, vol.8, issue.5, pp.556-567, 2000.
DOI : 10.1109/90.879343

]. D. Npar, M. Nace, and . Pioro, A tutorial on max-min fairness and its applications to routing and load-balancing in telecommunication networks, IEEE Communications Surveys and Tutorials

[. Ogryczak, M. Pioro, and A. Tomaszewski, Telecommunications network design and max-min optimization problem, Journal of Telecom. and Information Tech, vol.3, pp.43-56, 2005.

W. Ogryczak and T. Sliwinski, On Direct Methods for Lexicographic Min-Max Optimization, the ICCSA Conf, pp.802-811, 2006.
DOI : 10.1007/11751595_85

N. [. Parra-hernandez and . Dimopoulos, A new heuristic for solving the multichoice multidimensional knapsack problem. Systems, Man and Cybernetics, Part A, IEEE Transactions on, vol.35, issue.5, pp.708-717, 2005.

D. Pisinger, Core Problems in Knapsack Algorithms, Operations Research, vol.47, issue.4, pp.570-575, 1999.
DOI : 10.1287/opre.47.4.570

D. Pisinger, Where are the hard knapsack problems? Comput, Oper. Res, vol.32, issue.9, pp.2271-2284, 2005.

. Meng-shiuan, Y. Pan, and . Tseng, The orphan problem in zigbeebased wireless sensor networks, Proceedings of the 10th ACM International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems (MSWiM) BIBLIOGRAPHY [RB06] Bozidar Radunovic and Jean-Yves Le Boudec. A Unified Framework for Max-Min and Min-Max Fairness with Applications, pp.95-981073, 2006.

B. Raman and K. Chebrolu, Censor networks, ACM SIGCOMM Computer Communication Review, vol.38, issue.3, pp.75-78, 2008.
DOI : 10.1145/1384609.1384618

G. Robert and B. Dimitri, Data Networks
URL : https://hal.archives-ouvertes.fr/hal-01082038

[. Rangwala, R. Gummadi, R. Govindan, and K. Psounis, Interference-aware fair rate control in wireless sensor networks, ACM SIGCOMM, 2006.

[. Shahriar, M. M. Akbar, M. Rahman, and M. A. Newton, A multiprocessor based heuristic for multi-dimensional multiple-choice knapsack problem, The Journal of Supercomputing, vol.33, issue.3, pp.257-280, 2008.
DOI : 10.1007/s11227-007-0144-2

A. Sbihi, A best first search exact algorithm for the Multiple-choice Multidimensional Knapsack Problem, Journal of Combinatorial Optimization, vol.21, issue.3, pp.337-351, 2007.
DOI : 10.1007/s10878-006-9035-3
URL : https://hal.archives-ouvertes.fr/hal-00278065

M. Waselul, H. Sadid, S. Islam, and . Hasan, A new strategy for solving multiple-choice multiple-dimension knapsack problem in pram model, Asian Applied Computing Conference, 2005.

A. Sridharan and B. Krishnamachari, Max-min fair collision-free scheduling for wireless sensor networks, IEEE International Conference on Performance, Computing, and Communications, 2004, 2004.
DOI : 10.1109/PCCC.2004.1395103

A. Sridharan and B. Krishnamachari, Maximizing network utilization with max-min fairness in wireless sensor networks, International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), 2007.

S. Sarkar and L. Tassiulas, Fair allocation of discrete bandwidth layers in multicast networks, Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064), pp.1491-1500, 2000.
DOI : 10.1109/INFCOM.2000.832547

F. Sivrikaya and B. Yener, Time synchronization in sensor networks: a survey, IEEE Network, vol.18, issue.4, pp.45-50, 2004.
DOI : 10.1109/MNET.2004.1316761

Y. Toyoda, A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems, Management Science, vol.21, issue.12, pp.1417-1427, 1975.
DOI : 10.1287/mnsc.21.12.1417

R. [. Widmer, M. Denda, and . Mauve, A survey on TCP-friendly congestion control, IEEE Network, vol.15, issue.3, pp.28-37, 2001.
DOI : 10.1109/65.923938

C. Wan, S. B. Eisenman, and A. T. Campbell, CODA, Proceedings of the first international conference on Embedded networked sensor systems , SenSys '03, pp.266-279, 2003.
DOI : 10.1145/958491.958523

K. Wang, V. Sohraby, B. Lawrence, Y. Li, and . Hu, Priority-based congestion control in wireless sensor networks, SUTC '06: Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing, pp.22-31, 2006.

K. Wang, B. Sohraby, M. Li, Y. Daneshmand, and . Hu, A survey of transport protocols for wireless sensor networks, IEEE Network, vol.20, issue.3, pp.34-40, 2006.
DOI : 10.1109/MNET.2006.1637930

. Ch, V. Ykman-couvreur, . Nollet, . Fr, H. Catthoor et al., Fast multi-dimension multi-choice knapsack heuristic for mp-soc run-time management, System-on-Chip, 2006. International Symposium on, pp.1-4, 2006.

J. Yick, B. Mukherjee, and D. Ghosal, Wireless sensor network survey, Computer Networks, vol.52, issue.12, pp.2292-2330, 2008.
DOI : 10.1016/j.comnet.2008.04.002

F. Zhao and L. Guibas, Wireless Sensor Networks: An Information Processing Approach, 2004.

. J. Zigbee-alliance-document-053474r17-[-zl-], J. M. Zheng, and . Lee, Zigbee specification Low rate wireless personal area networks -ns2 simulation platform, 2008.

B. Han, J. Leblet, and G. Simon, Hard multidimensional multiple choice knapsack problems, an empirical study, Computers & Operations Research, vol.37, issue.1
DOI : 10.1016/j.cor.2009.04.006

B. Han, J. Leblet, and G. Simon, Query range problem in wireless sensor networks, IEEE Communications Letters, pp.55-57, 2009.
DOI : 10.1109/LCOMM.2009.081546

Y. Chen, B. Han, J. Leblet, G. Simon, and G. Straub, Network- Friendly Box-Powered Video Delivery System

B. Han and G. Simon, Optimizing Multi-hop Queries in ZigBee Based Multisink Sensor Networks, the 10th International Conference on Distributed Computing and Networking (ICDCN'09), pp.24-176, 2009.

B. Han and G. Simon, Fair Capacity Sharing Among Multiple Sinks in Wireless Sensor Networks, 2007 IEEE Internatonal Conference on Mobile Adhoc and Sensor Systems, pp.67-265, 2007.
DOI : 10.1109/MOBHOC.2007.4428641

B. Han, D. Xie, L. Tian, B. Ren, and S. Cheng, An Adaptive Location Service for Wireless Sensor Networks with Mobile Sinks, 2006 International Conference on Wireless and Mobile Communications (ICWMC'06), 2006.
DOI : 10.1109/ICWMC.2006.19

B. Han, J. Leblet, and G. Simon, On Sharing the Capacity of Hybrid Ad-Hoc Networks, the Autonomous and Spontaneous Networks Symposium, 2008.

B. Han and G. Simon, On the Optimality of Max-min Fair Query in Multi- Sink Wireless Sensor Networks, the Internal Workshop of Programme Initiative of GET, on Réseaux Spontanés, pp.30-31, 2007.

?. Glossary, A. Acknowledgement, and . Increase, Multiplicative Decrease AODV Ad hoc On-Demand Distance Vector Routing ARP Address Resolution Protocol ASK Amplitude-Shift Keying

?. and ?. Bblp, Branch and Bound with Linear Programming (algorithm for MMKP) BKP Bounded Knapsack Problem BPSK Binary Phase-Shift Keying

?. and ?. Cap, Contention Access Period CCA Clear Channel Assessment CCP Complementary Constructive Procedure (Hifi's MMKP Algorithm) CENS Center for Embedded Networked Sensing CDMA Code Division Multiple Access CFP Contention Free Period CGBA Column Generation Based Algorithm (Sbihi's MMKP Algorithm) CH1 Hiremath's Heuristic for MMKP