Sensor Redeployment Algorithm Based on Combined Virtual Forces in Three Dimensional Space
-
摘要: 无线传感器网络(Wireless sensor networks, WSNs)的重部署问题是提高无线传感器网络覆盖性能的一个重要问题, 实用化的重部署算法需要充分考虑传感器资源的有限性和实际布撒情况. 本文设计了基于组合虚拟力的分布式算法,该算法定义了传感器受到的邻居节点间的基于库仑力的斥力、 目标覆盖区域的基于胡克定律的中心吸引力和边界斥力, 综合这些力的合力以及单位能耗因素求得传感器节点每次移动的目标位置. 本文算法还给出了调整的终止条件以保证传感器能够重部署至合理位置. 理论论证和仿真实验表明,提出的基于组合虚拟力的重部署算法能使所有随机布撒的传感器节点在低能耗的情况下, 进入目标覆盖区域并在该区域内自组织成一个具有高覆盖性和重连通性的网络拓扑. 本文算法还解决了覆盖区域中存在障碍物的复杂情况.Abstract: The sensor redeployment problem is an important problem to improve sensor coverage in wireless sensor networks. A practical algorithm should consider the limitation of the sensor resources and the situation of the deployment. A distributed algorithm based on the combined virtual forces is designed in this paper. In this algorithm, the repulsive force from the 1-hop neighbors based on Coulomb's law, the attractive force from the sensing region center, and the repulsive force from the boundaries based on Hook's law are defined. Then the sensor position adjustment in one step is calculated by combining these forces mentioned above with the energy consumption factors. Meanwhile, the termination condition is also given in this algorithm to ensure the sensors can be redeployed to proper positions. Theoretical analysis and simulation results show that all of the sensors which are deployed in a random way will move into sensing region and self-organize a high-coverage and bi-connected network topology with low energy consumption. The obstacle problem can also be handled in this paper.
-
Key words:
- Wireless sensor networks (WSNs) /
- sensor redeployment /
- bi-connected /
- virtual forces
-
[1] Gage D W. Command control for many-robot systems. In: Proceedings of the 19th Annual AUVS Technical Symposium. Huntsville, USA: Unmanned Systems, 1992. 28-34[2] Shi Wei-Ren, Yuan Jiu-Yin, Lei Lu-Ning. Research on wireless sensor network coverage control algorithm. Acta Automatica Sinica, 2009, 35(5): 540-545(石为人, 袁久银, 雷璐宁. 无线传感器网络覆盖控制算法研究. 自动化学报, 2009, 35(5): 540-545)[3] Wang G L, Cao G H, Porta T F L. Movement-assisted sensor deployment. IEEE Transactions on Mobile Computing, 2006, 5(6): 640-652[4] Cortes J, Martinez S, Karatas T, Bullo F. Coverage control for mobile sensing networks. IEEE Transactions on Robotics and Automation, 2004, 20(2): 243-255[5] Heo N, Varshney P K. Energy-efficient deployment of intelligent mobile sensor networks. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 2005, 35(1): 78-92 [6] Jorgic M, Stojmenovic I, Hauspie M, Simplot-Ryl D. Localized algorithms for detection of critical nodes and links for connectivity in ad hoc networks. In: Proceedings of the 3rd Annual Mediterranean Ad Hoc Networking Workshop. Bodrum, Turkey: IEEE, 2004. 360-371[7] Das S, Liu H, Nayak A, Stojmenovic I. A localized algorithm for bi-connectivity of connected mobile robots. Telecommunication Systems, 2008, 40(3-4): 129-140[8] Zou Y, Chakrabarty K. Sensor deployment and target localization based on virtual forces. In: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer Communications. Washington D. C., USA: IEEE, 2003. 1293-1303[9] Howard A, Mataric M J, Sukhatme G S. Mobile sensor network deployment using potential field: a distributed scalable solution to the area coverage problem. In: Proceedings of the 6th International Symposium on Distributed Autonomous Robotic Systems. Fukuoka, Japan: Springer, 2002. 299-308[10] Tan G, Jarvis S A, Kermarrec A M. Connectivity-guaranteed and obstacle-adaptive deployment schemes for mobile sensor networks. In: Proceedings of the 28th International Conference on Distributed Computing Systems. Washington D. C., USA: IEEE, 2008. 429-437[11] Du Jun-Zhao, Liu Hui, Chen Ping, Wu Bo. Building the best reliable routing tree using link quality services in WSNs. Acta Automatica Sinica, 2007, 33(12): 1268-1274(杜军朝, 刘惠, 陈平, 武波. 无线传感器网络中基于链路层服务的最可靠路由路径建立算法. 自动化学报, 2007, 33(12): 1268-1274)[12] Liu H, Chu X W, Leung Y Y, Du R. Simple movement control algorithm for bi-connectivity in robotic sensor networks. IEEE Journal on Selected Areas in Communications, 2010, 28(7): 994-1005[13] Li X, Frey H, Santoro N, Stojmenovic I. Localized sensor self-deployment with coverage guarantee. In: Proceedings of the ACM SIGMOBILE Mobile Computing and Communications Review. New York, USA: ACM, 2008. 50-52[14] Lumelsky V J, Stepanov A A. Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape. Algorithmica, 1987, 2: 403-430
点击查看大图
计量
- 文章访问数: 2674
- HTML全文浏览量: 73
- PDF下载量: 1018
- 被引次数: 0