Distributed Barrier Coverage with Relocatable Sensors

详细信息    查看全文

• 作者：Mohsen Eftekhari (16)
  Paola Flocchini (17)
  Lata Narayanan (16)
  Jaroslav Opatrny (16)
  Nicola Santoro (18)
  
• 关键词：sensor networks ; barrier coverage ; distributed algorithms
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8576
• 期：1
• 页码：235-249
• 全文大小：307 KB
• 参考文献：1. Balister, P., Bollobas, B., Sarkar, A., Kumar, S.: Reliable density estimates for coverage and connectivity in thin strips of finite length. In: Proceedings of MobiCom 2007, pp. 75-6 (2007)
  2. Bhattacharya, B., Burmester, M., Hu, Y., Kranakis, E., Shi, Q., Wiese, A.: Optimal movement of mobile sensors for barrier coverage of a planar region. Theoretical Computer Science?410(52), 5515-528 (2009) CrossRef
  3. Chen, D.Z., Gu, Y., Li, J., Wang, H.: Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.?7357, pp. 177-88. Springer, Heidelberg (2012) CrossRef
  4. Cohen, R., Peleg, D.: Local spreading algorithms for autonomous robot systems. Theoretical Computer Science?399, 71-2 (2008) CrossRef
  5. Czyzowicz, J., Kranakis, E., Krizanc, D., Lambadaris, I., Narayanan, L., Opatrny, J., Stacho, L., Urrutia, J., Yazdani, M.: On minimizing the maximum sensor movement for barrier coverage of a line segment. In: Ruiz, P.M., Garcia-Luna-Aceves, J.J. (eds.) ADHOC-NOW 2009. LNCS, vol.?5793, pp. 194-12. Springer, Heidelberg (2009) CrossRef
  6. Czyzowicz, J., Kranakis, E., Krizanc, D., Lambadaris, I., Narayanan, L., Opatrny, J., Stacho, L., Urrutia, J., Yazdani, M.: On minimizing the sum of sensor movements for barrier coverage of a line segment. In: Nikolaidis, I., Wu, K. (eds.) ADHOC-NOW 2010. LNCS, vol.?6288, pp. 29-2. Springer, Heidelberg (2010) CrossRef
  7. Eftekhari, M., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S.: Distributed algorithms for barrier coverage using relocatable sensors. In: Proceedings of PODC 2013, pp. 383-92 (2013)
  8. Flocchini, P., Prencipe, G., Santoro, N.: Self-deployment of mobile sensors on a ring. Theoretical Computer Science?402(1), 67-0 (2008) CrossRef
  9. Flocchini, P., Prencipe, G., Santoro, N.: Computing by Mobile Robotic Sensors. In: ch. 21 [15] (2011)
  10. Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Morgan & Claypool (2012)
  11. Kumar, S., Lai, T.H., Arora, A.: Barrier coverage with wireless sensors. In: Proceedings of MobiCom 2005, pp. 284-98 (2005)
  12. Li, L., Zhang, B., Shen, X., Zheng, J., Yao, Z.: A study on the weak barrier coverage problem in wireless sensor networks. Computer Networks?55, 711-21 (2011) CrossRef
  13. Liu, B., Dousse, O., Wang, J., Saipulla, A.: Strong barrier coverage of wireless sensor networks. In: Proceedings of MobiHoc 2008, pp. 411-19 (2008)
  14. Mehrandish, M., Narayanan, L., Opatrny, J.: Minimizing the number of sensors moved on line barriers. In: Proceedings of WCNC, pp. 1464-469 (2011)
  15. Nikoletseas, S., Rolim, J. (eds.): Theoretical Aspects of Distributed Computing in Sensor Networks. Springer (2011)
  16. Saipulla, A., Westphal, C., Liu, B., Wang, J.: Barrier coverage of line-based deployed wireless sensor networks. In: Proceedings of IEEE INFOCOM 2009, pp. 127-35 (2009)
  17. Shen, C., Cheng, W., Liao, X., Peng, S.: Barrier coverage with mobile sensors. In: Proceedings of I-SPAN 2008, pp. 99-04 (2008)
  18. Wang, B.: Coverage Control in Sensor Networks. Springer (2010)
  19. Yamamoto, K., Izumi, T., Katayama, Y., Inuzuka, N., Wada, K.: The optimal tolerance of uniform observation error for mobile robot convergence. Theoretical Computer Science?444, 77-6 (2012) CrossRef
  
• 作者单位：Mohsen Eftekhari (16)
  Paola Flocchini (17)
  Lata Narayanan (16)
  Jaroslav Opatrny (16)
  Nicola Santoro (18)
  
  16. Dept. of Comp. Science and Soft. Eng., Concordia University, Montréal, Canada
  17. School of El. Eng. and Computer Science, University of Ottawa, Ottawa, Canada
  18. School of Computer Science, Carleton University, Ottawa, Canada
  
• ISSN：1611-3349

文摘

A wireless sensor can detect the presence of an intruder in its sensing range, and is said to cover the portion of a given barrier that intersects with its sensing range. Barrier coverage is achieved by a set of sensors if every point on the barrier is covered by some sensor in the set. Assuming n identical, anonymous, and relocatable sensors are placed initially at arbitrary positions on a line segment barrier, we are interested in the following question: under what circumstances can they independently make decisions and movements in order to reach final positions whereby they collectively cover the barrier? We assume each sensor repeatedly executes Look-Compute-Move cycles: it looks to find the positions of sensors in its visibility range, it computes its next position, and then moves to the calculated position. We consider only oblivious or memoryless sensors with sensing range r and visibility range 2r and assume that sensors can move at most distance r along the barrier in a move. Under these assumptions, it was shown recently that if the sensors are fully synchronized, then there exists an algorithm for barrier coverage even if sensors are unoriented, that is, they do not distinguish between left and right [7]. In this paper, we prove that orientation is critical to being able to solve the problem if we relax the assumption of tight synchronization. We show that if sensors are unoriented, then barrier coverage is unsolvable even in the semi-synchronous setting. In contrast, if sensors agree on a global orientation, then we give an algorithm for barrier coverage, even in the completely asynchronous setting. Finally, we extend the result of [4] and show that convergence to barrier coverage by unoriented sensors in the semi-synchronous model is possible with bounded visibility range 2r--em class="a-plus-plus">ρ (for arbitrarily small ρ--) and bounded mobility range r.