{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T18:16:39Z","timestamp":1774721799208,"version":"3.50.1"},"reference-count":140,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2009,9,28]],"date-time":"2009-09-28T00:00:00Z","timestamp":1254096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Wireless communication between sensors allows the formation of flexible sensor networks, which can be deployed rapidly over wide or inaccessible areas. However, the need to gather data from all sensors in the network imposes constraints on the distances between sensors. This survey describes the state of the art in techniques for determining the minimum density and optimal locations of relay nodes and ordinary sensors to ensure connectivity, subject to various degrees of uncertainty in the locations of the nodes.<\/jats:p>","DOI":"10.3390\/s91007664","type":"journal-article","created":{"date-parts":[[2009,9,28]],"date-time":"2009-09-28T13:03:56Z","timestamp":1254143036000},"page":"7664-7693","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":120,"title":["Connectivity, Coverage and Placement in Wireless Sensor Networks"],"prefix":"10.3390","volume":"9","author":[{"given":"Ji","family":"Li","sequence":"first","affiliation":[{"name":"ARC Special Research Centre for Ultra-Broadband Information Networks (CUBIN), University of Melbourne, Parkville 3010, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lachlan L.H.","family":"Andrew","sequence":"additional","affiliation":[{"name":"Centre for Advanced Internet Architectures (CAIA), Swinburne University of Technology, Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chuan Heng","family":"Foh","sequence":"additional","affiliation":[{"name":"School of Computer Engineering, Nanyang Technological University, 639798 Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe","family":"Zukerman","sequence":"additional","affiliation":[{"name":"Department of Electronic Engineering, City University of Hong Kong, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hsiao-Hwa","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Engineering Science, National Cheng Kung University, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2009,9,28]]},"reference":[{"key":"ref_1","unstructured":"Whitman, E.C. Sosus: The \u201cSecret Weapon\u201d of Undersea Surveillance. Available online: http:\/\/www.navy.mil\/navydata\/cno\/n87\/usw\/issue_25\/sosus.htm (accessed September 17, 2009)."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1247","DOI":"10.1109\/JPROC.2003.814918","article-title":"Sensor Networks: Evolution, Opportunities, and Challenges","volume":"91","author":"Chong","year":"2003","journal-title":"Proc. IEEE"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/S1389-1286(01)00302-4","article-title":"Wireless Sensor Networks: A Survey","volume":"38","author":"Akyildiz","year":"2002","journal-title":"Comput. Netw."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Sohraby, K., Minoli, D., and Znati, T. (2007). Wireless Sensor Networks: Technology, Protocols and Applications, John Wiley & Sons, Inc.","DOI":"10.1002\/047011276X"},{"key":"ref_5","unstructured":"Ni, S.-Y., Tseng, Y.-C., Chen, Y.-S., and Sheu, J.-P. The Broadcast Storm Problem in a Mobile Ad Hoc Network. Seattle, Washington, DC, New York, NY, USA."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Raghavendra, C.S., Sivalingam, K.M., and Znati, T. (2004). Wireless Sensor Networks, Springer.","DOI":"10.1007\/b117506"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1378","DOI":"10.1109\/TNET.2007.911432","article-title":"Lifetime Maximization for Connected Target Coverage in Wireless Sensor Networks","volume":"16","author":"Zhao","year":"2008","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Diestel, R. (2005). Graph Theory, Springer-Verlag. [electronic edition].","DOI":"10.4171\/owr\/2005\/03"},{"key":"ref_9","unstructured":"Krohn, A., Beigl, M., Decker, C., Riedel, T., Zimmer, T., and Varona, D.G. Increasing Connectivity in Wireless Sensor Network using Cooperative Transmission. Chicago, IL, USA."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B. (2001). Random Graphs, Cambridge University Press. [2nd ed.].","DOI":"10.1017\/CBO9780511814068"},{"key":"ref_11","first-page":"290","article-title":"On Random Graphs","volume":"6","year":"1959","journal-title":"Publ. Math."},{"key":"ref_12","first-page":"17","article-title":"On the Evolution of Random Graphs","volume":"5","year":"1960","journal-title":"Publ. Math. Inst. Hungarian Acad. Sci."},{"key":"ref_13","unstructured":"Atay, F., Stojmenovic, I., and Yanikomeroglu, H. (, January June). Generating Random Graphs for the Simulation of Wireless Ad Hoc, Actuator, Sensor, and Internet Networks. Helsinki, Finland."},{"key":"ref_14","unstructured":"Dowell, L.J., and Bruno, M.L. (, January March). Connectivity of Random Graphs and Mobile Networks: Validation of Monte Carlo Simulation Results. ACM, New York, NY, USA."},{"key":"ref_15","unstructured":"Gkantsidis, C., Mihail, M., and Zegura, E. (, January January). The Markov Chain Simulation Method for Generating Connected Power Law Random Graphs. Baltimore, MA, USA."},{"key":"ref_16","unstructured":"Ioannides, Y.M. Random Graphs and Social Networks: An Economics Perspective. Available online: http:\/\/ase.tufts.edu\/econ\/papers\/200518.pdf (accessed on April 1, 2008)."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2566","DOI":"10.1073\/pnas.012582999","article-title":"Random Graph Models of Social Networks","volume":"99","author":"Newman","year":"2002","journal-title":"Proc Nat Acad Sci, USA"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"2604","DOI":"10.1093\/bioinformatics\/btm370","article-title":"Exploring Biological Network Structure Using Exponential Random Graph Models","volume":"23","author":"Saul","year":"2007","journal-title":"Bioinformatics"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1214\/aoms\/1177706098","article-title":"Random Graphs","volume":"30","author":"Gilbert","year":"1959","journal-title":"Ann. Math. Statist."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1214\/aoms\/1177706204","article-title":"The Number of Components in Random Linear Graphs","volume":"30","author":"Austin","year":"1959","journal-title":"Ann. Math. Statist."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1073\/pnas.43.1.163","article-title":"Combinatorial Problems in the Theory of Graphs","volume":"43","author":"Ford","year":"1957","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1023\/A:1019186624837","article-title":"A New Approach to the Design and Analysis of Peer-to-Peer Mobile Networks","volume":"5","author":"Chlamtac","year":"1999","journal-title":"ACM Wirel. Netw."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Penrose, M.D. (2003). Random Geometric Graphs, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"ref_24","first-page":"533","article-title":"Random Plane Networks","volume":"9","author":"Gilbert","year":"1961","journal-title":"SIAM J."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"McEneaney, W.M., Yin, G.G., and Zhang, Q. (1998). Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming, Birkhauser Boston.","DOI":"10.1007\/978-1-4612-1784-8"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1109\/18.825799","article-title":"The Capacity of Wireless Networks","volume":"46","author":"Gupta","year":"2000","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_27","unstructured":"Ozgur, A., Leveque, O., and Tse, D. (, January May). Hierarchical Cooperation Achieves Linear Capacity Scaling in Ad Hoc Networks. Anchorage, Alaska, USA."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1250","DOI":"10.1214\/aop\/1176992809","article-title":"On Continuum Percolation","volume":"13","author":"Hall","year":"1985","journal-title":"Ann. Probab."},{"key":"ref_29","first-page":"856","article-title":"Coincidence of Critical Points in Percolation Problems","volume":"24","author":"Menshikov","year":"1986","journal-title":"Soviet Math. Dokl."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1111\/j.2517-6161.1954.tb00147.x","article-title":"Discussion on Symposium on Monte Carlo Methods","volume":"16","author":"Broadbent","year":"1954","journal-title":"J. Roy. Statist. Soc., Ser. B"},{"key":"ref_31","unstructured":"Broadbent, S.R., and Hammersley, J.M. Percolation Processes, I. Crystals and Mazes. Cambridge, UK."},{"key":"ref_32","unstructured":"Hammersley, J.M. Percolation Processes, II. The Connective Constant. Cambridge, UK."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1044","DOI":"10.1109\/18.42219","article-title":"Connectivity Properties of a Packet Radio Network Model","volume":"35","author":"Philips","year":"1989","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"L399","DOI":"10.1088\/0305-4470\/33\/42\/104","article-title":"Efficient Measurement of the Percolation Threshold for Fully Penetrable Discs","volume":"33","author":"Quintanilla","year":"2000","journal-title":"J. Phys. A: Math. Gen."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TMC.2003.1195149","article-title":"The Critical Transmitting Range for Connectivity in Sparse Wireless Ad Hoc Networks","volume":"2","author":"Santi","year":"2003","journal-title":"IEEE Trans. Mobile Comput."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/s11036-006-5188-7","article-title":"Connectivity in Wireless Ad-Hoc Networks with A Log-normal Radio Model","volume":"11","author":"Hekmat","year":"2006","journal-title":"Mobile Netw. Appl."},{"key":"ref_37","unstructured":"Ta, X., Mao, G., and Anderson, B.D.O. (, January April). On the Properties of Giant Component in Wireless Multi-hop Networks. Rio de Janeiro, Brazil."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Han, G., and Makowski, A.M. (2009). One-dimensional Geometric Random Graphs with Non-vanishing Densities I: A Strong Zero-one Law for Connectivity. IEEE Trans. Inform. Theory, in press.","DOI":"10.1109\/TIT.2009.2032799"},{"key":"ref_39","unstructured":"Han, G., and Makowski, A.M. (2009). Sensitivity of Critical Transmission Ranges to Node Placement Distributions. IEEE J. Sel. Area. Comm., in press."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1490","DOI":"10.1109\/18.133276","article-title":"On the Connectivity of Radio Networks","volume":"37","author":"Piret","year":"1991","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1002\/(SICI)1098-2418(199909)15:2<145::AID-RSA2>3.0.CO;2-G","article-title":"On k-Connectivity for a Geometric Random Graph","volume":"15","author":"Penrose","year":"1999","journal-title":"Random Struct. Algor."},{"key":"ref_42","unstructured":"Bettstetter, C. On the Minimum Node Degree and Connectivity of a Wireless Multihop Network. ACM, New York, NY, USA."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1109\/LCOMM.2002.804241","article-title":"On the Connectivity in Finite Ad Hoc Networks","volume":"6","author":"Desai","year":"2002","journal-title":"IEEE Comm. Lett."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1109\/LCOMM.2006.02006.","article-title":"Comments on \u201cOn the Connectivity in Finite Ad Hoc Networks\u201d","volume":"10","author":"Gore","year":"2006","journal-title":"IEEE Comm. Lett."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1109\/LCOMM.2006.1633322","article-title":"Correction to \u201cComments on 'On the Connectivity in Finite Ad Hoc Networks\u2019\u201d","volume":"10","author":"Gore","year":"2006","journal-title":"IEEE Comm. Lett."},{"key":"ref_46","first-page":"3739","article-title":"A Closed Form Network Connectivity Formula for One-Dimensional MANETs","volume":"6","author":"Foh","year":"2004","journal-title":"Proc. IEEE Int. Conf. Comm. (ICC)"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1109\/LCOMM.2006.1576556","article-title":"Meeting Connectivity Requirements in a Wireless Multihop Network","volume":"10","author":"Li","year":"2006","journal-title":"IEEE Comm. Lett."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"2082","DOI":"10.1109\/TSP.2003.814519","article-title":"Opportunistic Large Arrays: Cooperative Transmission in Wireless Multihop Ad Hoc Networks to Reach Far Distances","volume":"51","author":"Scaglione","year":"2003","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/11516798_26","article-title":"Directional Versus Omnidirectional Antennas for Energy Consumption and k-Connectivity of Networks of Sensors","volume":"3544","author":"Kranakis","year":"2005","journal-title":"Lect. Note. Comput. Sci."},{"key":"ref_50","unstructured":"Bhattacharya, B., Hu, Y., Shi, Q., Kranakis, E., and Krizanc, D. (, January May). Sensor Network Connectivity with Multiple Directional Antennae of a Given Angular Sum. Rome, Italy."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1023\/B:WINE.0000013081.09837.c0","article-title":"The Number of Neighbors Needed for Connectivity of Wireless Networks","volume":"10","author":"Xue","year":"2004","journal-title":"Wirel. Netw."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1239\/aap\/1198177228","article-title":"On the Connectivity and Diameter of Small-World Networks","volume":"39","author":"Ganesh","year":"2007","journal-title":"Adv. Appl. Probab."},{"key":"ref_53","unstructured":"Blough, D.M., Leoncini, M., Resta, G., and Santi, P. The K-Neigh Protocol for Symmetric Topology Control in Ad Hoc Networks. Annapolis, Maryland, USA."},{"key":"ref_54","unstructured":"Bettstetter, C. On the Connectivity of Wireless Multihop Networks with Homogeneous and Inho-mogeneous Range Assignment. Vancouver, British Columbia, Canada."},{"key":"ref_55","unstructured":"Sanchez, M., Manzoni, P., and Haas, Z.J. Determination of Critical Transmitting Ranges in Ad Hoc Networks. New Orleans, LA, USA."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1109\/TMC.2005.45","article-title":"The Critical Transmitting Range for Connectivity in Mobile Ad Hoc Networks","volume":"4","author":"Santi","year":"2005","journal-title":"IEEE Trans. Mobile Comput."},{"key":"ref_57","unstructured":"Wan, P.J., and Yi, C.W. Asymptotic Critical Transmission Radius and Critical Neighbor Number for k-Connectivity in Wireless Ad Hoc Networks. Roppongi Hills, Tokyo, Japan."},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1109\/TNET.2005.845546","article-title":"Impact of Interferences on Connectivity in Ad Hoc Networks","volume":"13","author":"Dousse","year":"2005","journal-title":"IEEE\/ACM Trans. Netw. (TON)"},{"key":"ref_59","unstructured":"Rappaport, T.S. (2004). Wireless Communications Principles and Practice, Pearson Education. [2nd ed.]."},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"2201","DOI":"10.1109\/26.392962","article-title":"Optimum Transmission Ranges in Multihop Packet Radio Networks in the presence of Fading","volume":"43","author":"Zorzi","year":"1995","journal-title":"IEEE Trans. Comm."},{"key":"ref_61","doi-asserted-by":"crossref","unstructured":"Bettstetter, C., and Hartmann, C. (2003, January September). Connectivity of Wireless Multihop Networks in a Shadow Fading Environment. San Diego, CA, USA.","DOI":"10.1145\/940997.940998"},{"key":"ref_62","unstructured":"Booth, L., Bruck, J., Cook, M., and Franceschetti, M. (4,, January June). Ad Hoc Wireless Networks with Noisy Links. Yokohama, Japan."},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"722","DOI":"10.1214\/aoap\/1050689601","article-title":"Covering Algorithms, Continuum Percolation and the Geometry of Wireless Networks","volume":"13","author":"Booth","year":"2003","journal-title":"Ann. Appl. Probab."},{"key":"ref_64","unstructured":"Dousse, O., Thiran, P., and Hasler, M. (2002, January June). Connectivity in Ad-Hoc and Hybrid Networks. New York, NY, USA."},{"key":"ref_65","doi-asserted-by":"crossref","first-page":"1009","DOI":"10.1109\/TIT.2006.890791","article-title":"Closing the Gap in the Capacity of Wireless Networks via Percolation Theory","volume":"53","author":"Franceschetti","year":"2007","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_66","unstructured":"Dousse, O., Franceschetti, M., and Thiran, P. Information Theoretic Bounds on the Throughput Scaling of Wireless Relay Networks. Miami, FL, USA."},{"key":"ref_67","unstructured":"Dousse, O., and Thiran, P. (, January March). Connectivity vs Capacity in Dense Ad Hoc Networks. Hong Kong, China."},{"key":"ref_68","unstructured":"Kleinrock, L., and Silvester, J. (, January December). Optimum Transmission Radii for Packet Radio Networks or Why Six is a Magic Number. Birmingham, Al, USA."},{"key":"ref_69","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1109\/TCOM.1984.1096061","article-title":"Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals","volume":"32","author":"Takagi","year":"1984","journal-title":"IEEE Trans. Comm."},{"key":"ref_70","unstructured":"Hajek, B. (, January March). Adaptive Transmission Strategies and Routing in Mobile Radio Networks. Princeton, NJ, USA."},{"key":"ref_71","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1109\/TCOM.1986.1096436","article-title":"Transmission Range Control in Multihop Packet Radio Networks","volume":"34","author":"Hou","year":"1986","journal-title":"IEEE Trans. Comm."},{"key":"ref_72","unstructured":"Hedrick, C. Available online: http:\/\/www.faqs.org\/rfcs\/rfc1058.html (accessed September 18, 2009)."},{"key":"ref_73","unstructured":"Moy, J. OSPF Version 2; Internet Request For Comments: RFC 1247. Available online: http:\/\/www.ietf.org\/rfc\/rfc1247.txt (accessed September 18, 2009)."},{"key":"ref_74","unstructured":"Biswas, S., and Morris, R. (, January August). Exor: Opportunistic Routing in Multihop Wireless Networks. Philadelphia, PA, USA."},{"key":"ref_75","doi-asserted-by":"crossref","unstructured":"Cui, T., Chen, L., Ho, T., Low, S.H., and Andrew, L.L.H. (2007, January October). Opportunistic Source Coding for Data Gathering in Wireless Sensor Networks. Pisa, Italy.","DOI":"10.1109\/MOBHOC.2007.4428675"},{"key":"ref_76","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1109\/MP.2003.1197877","article-title":"Sensor Networks: an Overview","volume":"22","author":"Tubaishat","year":"2003","journal-title":"IEEE Potent."},{"key":"ref_77","unstructured":"Heinzelman, W., Chandrakasan, A., and Balakrishnan, H. (, January January). Energy-efficient Communication Protocol for Wireless Microsensor Networks. Maui, Hawaii, USA."},{"key":"ref_78","unstructured":"Hussain, S., and Matin, A.W. Hierarchical Cluster-based Routing in Wireless Sensor Networks. Nashville, TN, USA."},{"key":"ref_79","unstructured":"Jiang, M., Li, J., and Tay, Y. (1999). IETF Internet Draft, MANET working group."},{"key":"ref_80","doi-asserted-by":"crossref","first-page":"1454","DOI":"10.1109\/49.779926","article-title":"CEDAR: A Core-Extraction Distributed Ad Hoc Routing Protocol","volume":"17","author":"Sivakumar","year":"1999","journal-title":"IEEE J. Sele. Area. Comm."},{"key":"ref_81","unstructured":"Manjeshwar, A., and Agrawal, D. (, January April). TEEN: A Protocol for Enhanced Efficiency in WSNs. San Francisco, CA, USA."},{"key":"ref_82","unstructured":"Manjeshwar, A., and Agrawal, D. (, January April). APTEEN: A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in WSNs. Ft. Lauderdale, FL, USA."},{"key":"ref_83","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/978-0-585-29603-6_5","article-title":"Dynamic Source Routing in Ad Hoc Wireless Networks","volume":"353","author":"Johnson","year":"1996","journal-title":"Mobile Comput."},{"key":"ref_84","unstructured":"Perkins, C. E., and Royer, E. M. (, January February). Ad Hoc On-Demand Distance Vector Routing. New Orleans, LA, USA."},{"key":"ref_85","unstructured":"Das, B., Sivakumar, E., and Bhargavan, V. (1997, January September). Routing in Ad Hoc Networks Using a Virtual Backbone. Las Vegas, NV, USA."},{"key":"ref_86","unstructured":"Wang, Y., Wang, W., and Li, X.Y. Distributed Low-cost Backbone Formation for Wireless Ad Hoc Networks. Urbana-Champaign, IL, USA."},{"key":"ref_87","unstructured":"Freeman, W.H. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness."},{"key":"ref_88","unstructured":"Li, J., Andrew, L.H.L., Foh, C.H., and Zukerman, M. (, January May). Sizes of Minimum Connected Dominating Sets of a Class of Wireless Sensor Networks. Beijing, China."},{"key":"ref_89","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/PL00009201","article-title":"Approximation Algorithms for Connected Dominating Sets","volume":"20","author":"Guha","year":"1998","journal-title":"Algorithmica"},{"key":"ref_90","unstructured":"Graham, R.L., Knuth, D.E., and Patashnik, O. (2002). Concrete Mathematics: A Foundation for Computer Science, Pearson Education. [2nd ed.]."},{"key":"ref_91","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on Two Problems in Connection with Graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numb. Math."},{"key":"ref_92","unstructured":"Cartigny, J., Simplot, D., and Stojmenovic, I. Localized Minimum-Energy Broadcasting in Ad-Hoc Networks. San Francisco, CA, USA."},{"key":"ref_93","doi-asserted-by":"crossref","unstructured":"Das, B., and Bharghavan, V. (1997). Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets. Proc. IEEE Int. Conf. Comm. (ICC), 376\u2013380.","DOI":"10.1109\/ICC.1997.605303"},{"key":"ref_94","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1109\/JCN.2002.6596929","article-title":"Distributed Heuristics for Connected Dominating Sets in Wireless Ad Hoc Networks","volume":"4","author":"Alzoubi","year":"2002","journal-title":"J. Comm. Netw."},{"key":"ref_95","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/net.3230250205","article-title":"Simple Heuristics for Unit Disk Graphs","volume":"25","author":"Marathe","year":"1995","journal-title":"Networks"},{"key":"ref_96","unstructured":"Alzoubi, K.M., Wan, P.J., and Frieder, O. (, January June). Message Optimal Connected Dominating Sets in Mobile Ad Hoc Networks. Lausanne, Switzerland."},{"key":"ref_97","doi-asserted-by":"crossref","unstructured":"Butenko, S., Murphey, R., and Pardalos, P.M. (2003). Cooperative Control: Models, Applications and Algorithms, Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4757-3758-5"},{"key":"ref_98","unstructured":"Cadei, M., Cheng, X., and Du, D.Z. Connected Domination in Ad Hoc Wireless Networks. Durham, NC, USA."},{"key":"ref_99","unstructured":"Ou, L., Sekercioglu, Y.A., and Mani, N. (, January March). A Low-cost Flooding Algorithm for Wireless Sensor Networks. Hong Kong, China."},{"key":"ref_100","unstructured":"Wu, J., and Li, H. (, January August). On Calculating Connected Dominating set for Efficient Routing in Ad Hoc Wireless Networks. New York, NY, USA."},{"key":"ref_101","unstructured":"Wu, J., Gao, M., and Stojmenovic, I. On Calculating Power-Aware Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks. Las Vegas, NV, USA."},{"key":"ref_102","doi-asserted-by":"crossref","unstructured":"Butenko, S., Murphey, R., and Pardalos, P. (2004). Recent Developments in Cooperative Contral and Optimization, Kluwer Academic Publishers. Chapter 4.","DOI":"10.1007\/978-1-4613-0219-3"},{"key":"ref_103","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00453-001-0101-z","article-title":"Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem","volume":"33","author":"Sanchis","year":"2002","journal-title":"Algorithmica"},{"key":"ref_104","unstructured":"Qayyum, A., Viennot, L., and Laouiti, A. (, January January). Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks. Hawaii, NJ, USA."},{"key":"ref_105","first-page":"27","article-title":"Computing Connected Dominated Sets with Multipoint Relays","volume":"1","author":"Adjih","year":"2005","journal-title":"Ad Hoc Sensor Netw."},{"key":"ref_106","unstructured":"Wu, J. (, January October). An Enhanced Approach to determine a small Forward Node Set Based on Multipoint Relays. Orlando, Florida, USA."},{"key":"ref_107","unstructured":"Chen, X., and Shen, J. (, January May). Reducing Connected Dominating Set Size with Multipoint Relays in Ad Hoc Wireless Networks. Hong Kong, China."},{"key":"ref_108","first-page":"866","article-title":"Extended Dominating-Set-Based Routing in Ad Hoc Wireless Networks with unidirectional Links","volume":"9","author":"Wu","year":"2002","journal-title":"IEEE T. Parall. Distr."},{"key":"ref_109","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1109\/TC.2006.40","article-title":"Extended Multipoint Relays to Determine Connected Dominating Sets in MANETs","volume":"55","author":"Wu","year":"2006","journal-title":"IEEE Trans. Comput."},{"key":"ref_110","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1109\/COMST.2006.283820","article-title":"A Survey of Multipoint Relay Based Broadcast Schemes in Wireless Ad Hoc Networks","volume":"8","author":"Ou","year":"2006","journal-title":"IEEE Communications Surveys and Tutorials"},{"key":"ref_111","unstructured":"Dhillon, S.S., and Chakrabarty, K. (, January March). Sensor Placement for Effective Coverage and Surveillance in Distributed Sensor Networks. New Orleans, LA, USA."},{"key":"ref_112","unstructured":"O'Rourke, J. (1987). Art Gallery Theorems and Algorithms, Oxford University Press, Inc."},{"key":"ref_113","unstructured":"Gonz\u00f3lez-Banos, H. Randomized Art-Gallery Algorithm for Sensor Placement. Medford, Massachusetts, USA."},{"key":"ref_114","first-page":"89","article-title":"Maintaining Sensing Coverage and Connectivity in Large Sensor Networks","volume":"1","author":"Zhang","year":"2005","journal-title":"Ad Hoc Sensor Wirel. Netw."},{"key":"ref_115","doi-asserted-by":"crossref","first-page":"665","DOI":"10.2307\/2371320","article-title":"The Number of Circles Covering a Set","volume":"61","author":"Kershner","year":"1939","journal-title":"Am. J. Math."},{"key":"ref_116","doi-asserted-by":"crossref","first-page":"2907","DOI":"10.3390\/S7112907","article-title":"Novel Deployment Schemes for Mobile Sensor Networks","volume":"7","author":"Chen","year":"2007","journal-title":"Sensors"},{"key":"ref_117","doi-asserted-by":"crossref","first-page":"2792","DOI":"10.3390\/s8042792","article-title":"Relocating Sensor Nodes to Maximize Cumulative Connected Coverage in Wireless Sensor Networks","volume":"8","author":"Coskun","year":"2008","journal-title":"Sensors"},{"key":"ref_118","doi-asserted-by":"crossref","first-page":"1625","DOI":"10.3390\/s90301625","article-title":"A Tabu Search WSN Deployment Method for Monitoring Geographically Irregular Distributed Events","volume":"9","author":"Aitsaadi","year":"2009","journal-title":"Sensors"},{"key":"ref_119","unstructured":"Biagioni, E.S., and Sasaki, G. (, January January). Wireless Sensor Placement for Reliable and Efficient Data Collection. Big Island, HI, USA."},{"key":"ref_120","unstructured":"Iyengar, R., Kar, K., and Banerjee, S. (, January May). Low-coordination Topologies for Redundancy in Sensor Networks. Urbana-Champaign, IL, USA."},{"key":"ref_121","doi-asserted-by":"crossref","unstructured":"Bai, X., Santosh, K., Dong, X., Yun, Z., and Ten, H.L. (2006, January May). Deploying Wireless Sensors to Achieve Both Coverage and Connectivity. Florence, Italy, May.","DOI":"10.1145\/1132905.1132921"},{"key":"ref_122","unstructured":"Bai, X., Xuan, D., Yun, Z., Lai, T.H., and Jia, W. (, January May). Complete Optimal Deployment Patterns for Full-Coverage and k-Connectivity (k \u2264 6) Wireless Sensor Networks. Hong Kong, China."},{"key":"ref_123","unstructured":"Wang, Y.C., Hu, C.C., and Tseng, Y.C. (, January July). Efficient Deployment Algorithms for Ensuring Coverage and Connectivity of Wireless Sensor Networks. Visegrad-Budapest, Hungary."},{"key":"ref_124","unstructured":"Khan, S.U. (, January April). Approximate Optimal Sensor Placements in Grid Sensor Fields. Dublin, Ireland."},{"key":"ref_125","doi-asserted-by":"crossref","first-page":"1448","DOI":"10.1109\/TC.2002.1146711","article-title":"Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks","volume":"51","author":"Chakrabarty","year":"2002","journal-title":"IEEE Trans. Comp."},{"key":"ref_126","first-page":"43","article-title":"A Near-Optimal Sensor Placement Algorithm to Achieve Complete Coverage\/Discrimination in Sensor Networks","volume":"9","author":"Lin","year":"2005","journal-title":"IEEE Comm. Lett."},{"key":"ref_127","unstructured":"Ishizuka, M., and Aida, M. (, January March). Performance Study of Node Placement in Sensor Networks. Hachioji, Tokyo, Japan."},{"key":"ref_128","doi-asserted-by":"crossref","first-page":"401","DOI":"10.6028\/jres.106.017","article-title":"Distribution of Link Distances in a Wireless Network","volume":"106","author":"Miller","year":"2001","journal-title":"J. Res. Natl. Instit. Stan."},{"key":"ref_129","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1023\/B:WINE.0000036457.00804.e9","article-title":"A Statistical Analysis of the Long-run Node Spatial Distribution in Mobile Ad Hoc Networks","volume":"10","author":"Blough","year":"2004","journal-title":"Wirel. Netw."},{"key":"ref_130","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s11276-006-0724-8","article-title":"Relay Sensor Placement in Wireless Sensor Networks","volume":"14","author":"Cheng","year":"2008","journal-title":"Wirel. Netw."},{"key":"ref_131","unstructured":"Hao, B., Tang, J., and Xue, G. Fault-Tolerant Relay Node Placement in Wireless Sensor Networks: Formulation and Approximation."},{"key":"ref_132","unstructured":"Pan, J., Hou, Y.T., Cai, L., Shi, Y., and Shen, S.X. Topology control for Wireless Sensor Networks. San Diego, CA, USA."},{"key":"ref_133","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/j.comcom.2004.12.032","article-title":"Relay Node Placement in Large Scale Wireless Sensor Networks","volume":"29","author":"Tang","year":"2006","journal-title":"Comput. Comm.s"},{"key":"ref_134","unstructured":"Zhang, W., Xue, G., and Misra, S. (, January May). Fault-Tolerant Relay Node Placement in Wireless Sensor Networks: Problems and Algorithms. Anchorage, AK, USA."},{"key":"ref_135","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0020-0190(98)00201-4","article-title":"Steiner Tree Problem with Minimum Number of Steiner Points and Bounded Edge-Length","volume":"69","author":"Lin","year":"1999","journal-title":"Inf. Proc. Lett."},{"key":"ref_136","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1023\/A:1008384012064","article-title":"Approximations for Steiner Trees with Minimum Number of Steiner Points","volume":"18","author":"Chen","year":"2000","journal-title":"J. Glob. Opt."},{"key":"ref_137","unstructured":"Kashyap, A., Khuller, S., and Shayman, M. Relay Placement for Higher Order Connectivity in Wireless Sensor Networks. Barcelona, Spain."},{"key":"ref_138","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1109\/TC.2007.250629","article-title":"Relay Node Placement in Wireless Sensor Networks","volume":"56","author":"Lloyd","year":"2007","journal-title":"IEEE Trans. Comoput."},{"key":"ref_139","unstructured":"Misra, S., Hong, S.D., Xue, G., and Tang, J. (, January April). Constrained Relay Node Placement in Wireless Sensor Networks to Meet Connectivity and Survivability Requirements. Phoenix, AZ, USA."},{"key":"ref_140","unstructured":"Srinivas, A., and Modiano, E. (, January April). Joint Node Placement and Assignment for Throughput Optimization in Mobile Backbone Networks. Phoenix, AZ, USA."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/9\/10\/7664\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:11:15Z","timestamp":1760220675000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/9\/10\/7664"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,28]]},"references-count":140,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2009,10]]}},"alternative-id":["s91007664"],"URL":"https:\/\/doi.org\/10.3390\/s91007664","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9,28]]}}}