{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:47Z","timestamp":1750306127847,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,8,1]],"date-time":"2017-08-01T00:00:00Z","timestamp":1501545600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation (USA) via an Indo-US collaborative project titled Wireless Sensor Networks for Protecting Wildlife and Humans,"},{"name":"J.C. Bose National Fellowship"},{"name":"Department of Electronics and Information Technology"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2017,8,31]]},"abstract":"<jats:p>Motivated by the need for impromptu or as-you-go deployment of wireless sensor networks in some situations, we study the problem of optimal sequential deployment of wireless sensors and relays along a line (e.g., a forest trail) of unknown length. Starting from the sink node (e.g., a base station), a \u201ddeployment agent\u201e walks along the line, stops at equally spaced points (\u201dpotential\u201e relay locations), placing relays at some of these points, until he reaches a location at which the source node (i.e., the sensor) needs to be placed, the objective being to create a multihop wireless relay network between the source and the sink. The deployment agent decides whether to place a relay or not at each of the potential locations, depending upon the link quality measurements to the previously placed relays.<\/jats:p>\n          <jats:p>In this article, we seek to design efficient deployment algorithms for this class of problems, to achieve the objective of 2-connectivity in the deployed network. We ensure multi-connectivity by allowing each node to communicate with more than one neighbouring node. By proposing a network cost objective that is additive over the deployed relays, we formulate the relay placement problem as a Markov decision process. We provide structural results for the optimal policy and evaluate the performance of the optimal policy via numerical exploration. Computation of such an optimal deployment policy requires a statistical model for radio propagation; we extract this model from the raw data collected via measurements in a forestlike environment. To validate the results obtained from the numerical study, we provide an experimental study of algorithms for 2-connected network deployment.<\/jats:p>","DOI":"10.1145\/3085577","type":"journal-article","created":{"date-parts":[[2017,8,1]],"date-time":"2017-08-01T19:20:44Z","timestamp":1501615244000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Measurement Based As-You-Go Deployment of Two-Connected Wireless Relay Networks"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6548-6692","authenticated-orcid":false,"given":"Avishek","family":"Ghosh","sequence":"first","affiliation":[{"name":"Indian Institute of Science, Bangalore, India"}]},{"given":"Arpan","family":"Chattopadhyay","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bangalore, India"}]},{"given":"Anish","family":"Arora","sequence":"additional","affiliation":[{"name":"The Ohio State University, Columbus, USA"}]},{"given":"Anurag","family":"Kumar","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bangalore, India"}]}],"member":"320","published-online":{"date-parts":[[2017,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"https:\/\/tools.ietf.org\/html\/rfc6550.  https:\/\/tools.ietf.org\/html\/rfc6550."},{"key":"e_1_2_1_2_1","unstructured":"http:\/\/www.willow.co.uk\/TelosB_Datasheet.pdf.  http:\/\/www.willow.co.uk\/TelosB_Datasheet.pdf."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/PIMRC.2012.6362853"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/MWC.2014.7000982"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICECTECH.2011.5941646"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/GLOCOM.2007.234"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17520-6_15"},{"volume-title":"Dynamic Programming and Optimal Control","author":"Bertsekas D. P.","key":"e_1_2_1_8_1","unstructured":"D. P. Bertsekas .2007. Dynamic Programming and Optimal Control , Vol. II . Athena Scientific . D. P. Bertsekas.2007. Dynamic Programming and Optimal Control, Vol. II. Athena Scientific."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(85)90288-4"},{"key":"e_1_2_1_10_1","volume-title":"2014. QoS aware and survivable network design for planned wireless sensor networks.","author":"Bhattacharya A.","year":"2014","unstructured":"A. Bhattacharya and A. Kumar . 2014. QoS aware and survivable network design for planned wireless sensor networks. Retrieved from http:\/\/arxiv.org\/abs\/1110.4746 ( 2014 ). A. Bhattacharya and A. Kumar.2014. QoS aware and survivable network design for planned wireless sensor networks. Retrieved from http:\/\/arxiv.org\/abs\/1110.4746 (2014)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMSNETS.2013.6465582"},{"key":"e_1_2_1_12_1","volume-title":"Doksum","author":"Bickel Peter J.","year":"2001","unstructured":"Peter J. Bickel and Kjell A . Doksum . 2001 . Mathematical Statistics, vol. I . Prentice Hall , Englewood Cliffs, NJ. Peter J. Bickel and Kjell A. Doksum. 2001. Mathematical Statistics, vol. I. Prentice Hall, Englewood Cliffs, NJ."},{"volume-title":"Proceedings of the 11th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt\u201813)","author":"Chattopadhyay A.","key":"e_1_2_1_13_1","unstructured":"A. Chattopadhyay , M. Coupechoux , and A. Kumar . 2013. Measurement based impromptu deployment of a multi-hop wireless relay network . In Proceedings of the 11th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt\u201813) . IEEE. A. Chattopadhyay, M. Coupechoux, and A. Kumar.2013. Measurement based impromptu deployment of a multi-hop wireless relay network. In Proceedings of the 11th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt\u201813). IEEE."},{"key":"e_1_2_1_14_1","volume-title":"2015. Sequential decision algorithms for measurement-based impromptu deployment of a wireless relay network along a line","author":"Chattopadhyay A.","year":"2015","unstructured":"A. Chattopadhyay , M. Coupechoux , and A. Kumar . 2015. Sequential decision algorithms for measurement-based impromptu deployment of a wireless relay network along a line . IEEE\/ACM Trans. Netw. (Accepted) , retrieved from http:\/\/arxiv.org\/abs\/1502.06878 ( 2015 ). A. Chattopadhyay, M. Coupechoux, and A. Kumar.2015. Sequential decision algorithms for measurement-based impromptu deployment of a wireless relay network along a line. IEEE\/ACM Trans. Netw. (Accepted), retrieved from http:\/\/arxiv.org\/abs\/1502.06878 (2015)."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the IEEE International Conference on Mobile Ad hoc and Sensor Systems (MASS\u201814)","author":"Chattopadhyay A.","year":"2014","unstructured":"A. Chattopadhyay , A. Ghosh , A. S. Rao , B. Dwivedi , S. V. R. Anand , M. Coupechoux , and A. Kumar . 2014. Impromptu deployment of wireless relay networks: Experiences along a forest trail . In Proceedings of the IEEE International Conference on Mobile Ad hoc and Sensor Systems (MASS\u201814) , retrieved from http:\/\/arxiv.org\/abs\/1409.3940 ( 2014 ). A. Chattopadhyay, A. Ghosh, A. S. Rao, B. Dwivedi, S. V. R. Anand, M. Coupechoux, and A. Kumar.2014. Impromptu deployment of wireless relay networks: Experiences along a forest trail. In Proceedings of the IEEE International Conference on Mobile Ad hoc and Sensor Systems (MASS\u201814), retrieved from http:\/\/arxiv.org\/abs\/1409.3940 (2014)."},{"volume-title":"Proceedings of the 8th ACM Conference on Embedded Networked Sensor Systems (SenSys\u201810)","author":"Dyo V.","key":"e_1_2_1_16_1","unstructured":"V. Dyo , S. A. Ellwood , D. W. Macdonald , A. Markham , C. Mascolo , B. Pasztor , S. Scellato , N. Trigoni , R. Wohlers , and K. Yousef . 2011. Evolution and sustainability of a wildlife monitoring sensor network . In Proceedings of the 8th ACM Conference on Embedded Networked Sensor Systems (SenSys\u201810) . ACM, 127--140. V. Dyo, S. A. Ellwood, D. W. Macdonald, A. Markham, C. Mascolo, B. Pasztor, S. Scellato, N. Trigoni, R. Wohlers, and K. Yousef.2011. Evolution and sustainability of a wildlife monitoring sensor network. In Proceedings of the 8th ACM Conference on Embedded Networked Sensor Systems (SenSys\u201810). ACM, 127--140."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/MPRV.2009.91"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Meijuan Gao Fan Zhang and Jingwen Tian.2008. Wireless mesh network for emergency response system based on embedded system.  Meijuan Gao Fan Zhang and Jingwen Tian.2008. Wireless mesh network for emergency response system based on embedded system.","DOI":"10.1109\/CCDC.2008.4598221"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SPCOM.2014.6983982"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1049\/el:19911328"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019625207705"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1814433.1814438"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/PIMRC.2011.6139647"},{"key":"e_1_2_1_24_1","volume-title":"2011. Multichannel access for bandwidth improvement in IEEE 802.15.4 wireless sensor networks.","author":"Lohier S.","year":"2011","unstructured":"S. Lohier , A. Rachedi , I. Salhi , and E. Livolant . 2011. Multichannel access for bandwidth improvement in IEEE 802.15.4 wireless sensor networks. Retrieved from https:\/\/hal-enpc.archives-ouvertes.fr\/hal-00680871\/document ( 2011 ). S. Lohier, A. Rachedi, I. Salhi, and E. Livolant.2011. Multichannel access for bandwidth improvement in IEEE 802.15.4 wireless sensor networks. Retrieved from https:\/\/hal-enpc.archives-ouvertes.fr\/hal-00680871\/document (2011)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCIS.2008.4717943"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/570738.570751"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/NCC.2012.6176830"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/E2EMON.2007.375316"},{"key":"e_1_2_1_29_1","volume-title":"2012. Optimal sequential wireless relay placement on a random lattice path.","author":"Sinha A.","year":"2012","unstructured":"A. Sinha , A. Chattopadhyay , K. P. Naveen , M. Coupechoux , and A. Kumar . 2012. Optimal sequential wireless relay placement on a random lattice path. Retrieved from http:\/\/arxiv.org\/abs\/1207.6318 ( 2012 ). A. Sinha, A. Chattopadhyay, K. P. Naveen, M. Coupechoux, and A. Kumar.2012. Optimal sequential wireless relay placement on a random lattice path. Retrieved from http:\/\/arxiv.org\/abs\/1207.6318 (2012)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247660.1247673"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2011.2166773"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISSNIP.2015.7106914"},{"volume-title":"Proceedings of the 2013 11th International Symposium on Modeling 8 Optimization in Mobile, Ad Hoc 8 Wireless Networks (WiOpt\u201813)","author":"Vodel Matthias","key":"e_1_2_1_33_1","unstructured":"Matthias Vodel and Wolfram Hardt .2013. Energy-efficient communication in distributed, embedded systems . In Proceedings of the 2013 11th International Symposium on Modeling 8 Optimization in Mobile, Ad Hoc 8 Wireless Networks (WiOpt\u201813) . IEEE, 641--647. Matthias Vodel and Wolfram Hardt.2013. Energy-efficient communication in distributed, embedded systems. In Proceedings of the 2013 11th International Symposium on Modeling 8 Optimization in Mobile, Ad Hoc 8 Wireless Networks (WiOpt\u201813). IEEE, 641--647."}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3085577","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3085577","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:37:01Z","timestamp":1750217821000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3085577"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/3085577"],"URL":"https:\/\/doi.org\/10.1145\/3085577","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2017,8]]},"assertion":[{"value":"2016-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}