research-article

Movement-Assisted Sensor Deployment

Authors:

Thomas F. La PortaAuthors Info & Claims

IEEE Transactions on Mobile Computing, Volume 5, Issue 6

Pages 640 - 652

https://doi.org/10.1109/TMC.2006.80

Published: 01 June 2006 Publication History

Abstract

Adequate coverage is very important for sensor networks to fulfill the issued sensing tasks. In many working environments, it is necessary to make use of mobile sensors, which can move to the correct places to provide the required coverage. In this paper, we study the problem of placing mobile sensors to get high coverage. Based on Voronoi diagrams, we design two sets of distributed protocols for controlling the movement of sensors, one favoring communication and one favoring movement. In each set of protocols, we use Voronoi diagrams to detect coverage holes and use one of three algorithms to calculate the target locations of sensors if holes exist. Simulation results show the effectiveness of our protocols and give insight on choosing protocols and calculation algorithms under different application requirements and working conditions.

References

[1]

“Berkeley Sensor and Actuator Center,”

[2]

“Wireless Sensing Networks,”

[3]

“US Naval Observatory (USNO) GPS Operations,”

[4]

F. Aurenhammer, “Voronoi Diagrams— A Survey of a Fundamental Geometric Data Structure,” ACM Computing Surveys, vol. 23, pp. 345-405, 1991.

Digital Library

[5]

T. Clouqueur, V. Phipatanasuphorn, P. Ramanathan, and K.K. Saluja, “Sensor Deployment Strategy for Target Detection,” Proc. First ACM Int'l Workshop Wireless Sensor Networks and Applications, 2002.

Digital Library

[6]

D. Koditschek, “Planning and Control via Potential Functions,” Robotics Rev. I, pp. 349-367, 1989.

Digital Library

[7]

D. Niculescu and B. Nath, “Ad Hoc Positioning Systems (APS) Using AoA,” Proc. IEEE Infocom, 2003.

[8]

F. Zhao and L. Guibas, Wireless Sensor Networks. Morgan Kaufmann, 2004.

[9]

S. Fortune, D. Du, and F. Hwang, “Voronoi Diagrams and Delaunay Triangulations,” Euclidean Geometry and Computers, 1992.

[10]

G. Wang, G. Cao, and T. La Porta, “Movement-Assisted Sensor Deployment,” Proc. IEEE Infocom, March 2004.

[11]

W.R. Heinzelman, J. Kulik, and H. Balakrishnan, “Adaptive Protocols for Information Dissemination in Wireless Sensor Network,” Proc. ACM MobiCom, 1999.

Digital Library

[12]

A. Howard, M.J. Mataric, and G.S. Sukhatme, “An Incremental Self-Deployment Algorithm for Mobile Sensor Networks,” Autonomous Robots, special issue on intelligent embedded systems, Sept. 2002.

Digital Library

[13]

A. Howard, M.J. Mataric, and G.S. Sukhatme, “Mobile Sensor Networks Deployment Using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem,” Proc. Sixth Int'l Symp. Distributed Autonomous Robotics Systems, June 2002.

[14]

L. Hu and D. Evans, “Localization for Mobile Sensor Networks,” Proc. ACM MobiCom, 2004.

Digital Library

[15]

C. Intanagonwiwat, R. Govindan, and D. Estrin, “Directed Diffusion: A Scalable and Robust Communication,” Proc. ACM MobiCom, 2000.

Digital Library

[16]

J. Nocedal and S.J. Wright, Numerical Optimization. New York: Springer, 1999.

[17]

J. Lengyel, M. Reichert, B. Donald, and D. Greenberg, “Real-Time Robot Motion Planning Using Rasterizing Computer Graphics Hardware,” Proc. SIGGRAPH, 1990.

Digital Library

[18]

Q. Li, M. De Rosa, and D. Rus, “Distributed Algorithms for Guiding Navigation across a Sensor Network,” Proc. ACM MobiCom, 2003.

Digital Library

[19]

N. Megiddo, “Linear-Time Algorithms for Linear Programming in $R^3$ and Related Problems,” SIAM J. Computing, vol. 12, pp. 759-776, 1983.

[20]

S. Meguerdichian, F. Koushanfar, G. Qu, and M. Potkonjak, “Exposure In Wireless Ad-Hoc Sensor Networks,” Proc. ACM MobiCom, 2001.

Digital Library

[21]

S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M.B. Srivastava, “Coverage Problems in Wireless Ad-Hoc Sensor Network,” Proc. IEEE Infocom, 2001.

[22]

N. Patwari and A. HeroIII, “Using Proximity and Quantized RSS for Sensor Location in Wireless Location in Wireless Networks,” Proc. Workshop Wireless Sensor Networks and Applications, 2003.

Digital Library

[23]

C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Dover, 1998.

Digital Library

[24]

G.J. Pottie and W.J. Kaiser, “Wireless Integrated Network Sensors,” Comm. ACM, May 2000.

Digital Library

[25]

A. Savvides, C. Han, and M.B. Strivastava, “Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors,” Proc. ACM MobiCom, 2001.

Digital Library

[26]

G.T. Sibley, M.H. Rahimi, and G.S. Sukhatme, “Robomote: A Tiny Mobile Robot Platform for Large-Scale Sensor Networks,” Proc. IEEE Int'l Conf. Robotics and Automation, 2002.

[27]

S. Skyum, “A Simple Algorithm for Computing the Smallest Enclosing Circle,” Information Processing Letters, vol. 37, pp. 121-125, 1991.

Digital Library

[28]

K. Sohrabi, J. Gao, V. Ailawadhi, and G.J. Pottie, “Protocols for Self-Organization of a Wireless Sensor Network,” IEEE Personal Comm., vol. 7, no. 5, pp. 16-27, Oct. 2000.

[29]

E. Welzl, “Smallest Enclosing Disks (Balls and Ellipsoids),” New Results and New Trends in Computer Science, pp. 359-370, 1991.

[30]

Y. Zou and K. Chakrabarty, “Sensor Deployment and Target Localization Based on Virtual Forces,” Proc. IEEE Infocom, 2003.

Cited By

Mazaheri HGoli SNourollah A(2024)A survey of 3D Space Path-Planning Methods and AlgorithmsACM Computing Surveys10.1145/367389657:1(1-32)Online publication date: 7-Oct-2024
https://dl.acm.org/doi/10.1145/3673896
Karimi-Bidhendi SGeraci GJafarkhani H(2024)Optimizing Cellular Networks for UAV Corridors via Quantization TheoryIEEE Transactions on Wireless Communications10.1109/TWC.2024.342089823:10_Part_3(14924-14939)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1109/TWC.2024.3420898
Das SSaha DSinha BSinha K(2024)Strategic placement of access points for message communication in a smart building environmentInnovations in Systems and Software Engineering10.1007/s11334-022-00466-220:3(425-433)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11334-022-00466-2
Show More Cited By

Index Terms

Movement-Assisted Sensor Deployment
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Networks

Recommendations

A Delaunay Triangulation based method for wireless sensor network deployment

To obtain a satisfied performance of wireless sensor network, an adaptable sensor deployment method for various applications is essential. In this paper, we propose a centralized and deterministic sensor deployment method, DT-Score (Delaunay ...
On mobile sensor assisted field coverage

Providing field coverage is a key task in many sensor network applications. With unevenly distributed static sensors, quality coverage with acceptable network lifetime is often difficult to achieve. Fortunately, recent advances on embedded and robotic ...
Deployment and reallocation in mobile survivability-heterogeneous wireless sensor networks for barrier coverage

Barrier coverage is a widely adopted coverage model for intruder surveillance application in wireless sensor networks. However, when sensor nodes are deployed outdoors, they are subject to environmental detriments and will be failed while operating in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Mobile Computing

IEEE Transactions on Mobile Computing Volume 5, Issue 6

June 2006

160 pages

ISSN:1536-1233

Issue’s Table of Contents

Copyright © 2006.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 June 2006

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

131
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mazaheri HGoli SNourollah A(2024)A survey of 3D Space Path-Planning Methods and AlgorithmsACM Computing Surveys10.1145/367389657:1(1-32)Online publication date: 7-Oct-2024
https://dl.acm.org/doi/10.1145/3673896
Karimi-Bidhendi SGeraci GJafarkhani H(2024)Optimizing Cellular Networks for UAV Corridors via Quantization TheoryIEEE Transactions on Wireless Communications10.1109/TWC.2024.342089823:10_Part_3(14924-14939)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1109/TWC.2024.3420898
Das SSaha DSinha BSinha K(2024)Strategic placement of access points for message communication in a smart building environmentInnovations in Systems and Software Engineering10.1007/s11334-022-00466-220:3(425-433)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11334-022-00466-2
Sadeghi Ghahroudi MShahrabi AGhoreyshi SAlfouzan F(2023)Distributed Node Deployment Algorithms in Mobile Wireless Sensor Networks: Survey and ChallengesACM Transactions on Sensor Networks10.1145/357903419:4(1-26)Online publication date: 10-Jul-2023
https://dl.acm.org/doi/10.1145/3579034
Zulfiqar RJavid TAli ZUddin V(2023)Novel metaheuristic routing algorithm with optimized energy and enhanced coverage for WSNsAd Hoc Networks10.1016/j.adhoc.2023.103133144:COnline publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.adhoc.2023.103133
Dutta SGiri AGiri DNeogy SDahal KChen W(2023)Optimum Node Deployment Policy (ONDP) for WSN: Trade-off Between Maximization of Area Coverage and LifetimeWireless Personal Communications: An International Journal10.1007/s11277-023-10804-7133:2(1055-1080)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1007/s11277-023-10804-7
Mohar SGoyal SKaur R(2023)Exploration of different topologies for optimal sensor nodes deployment in wireless sensor networks using jaya-sine cosine optimization algorithmThe Journal of Supercomputing10.1007/s11227-023-05147-w79:12(13001-13030)Online publication date: 21-Mar-2023
https://dl.acm.org/doi/10.1007/s11227-023-05147-w
Ji KZhang QYuan ZCheng HYu D(2022)A virtual force interaction scheme for multi-robot environment monitoringRobotics and Autonomous Systems10.1016/j.robot.2021.103967149:COnline publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.robot.2021.103967
Martínez DMojica-Nava E(2022)Distortion based potential game for distributed coverage controlInformation Sciences: an International Journal10.1016/j.ins.2022.03.090600:C(209-225)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1016/j.ins.2022.03.090
Chaturvedi PDaniel A(2022)A Comprehensive Review on Scheduling Based Approaches for Target Coverage in WSNWireless Personal Communications: An International Journal10.1007/s11277-021-09281-7123:4(3147-3199)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s11277-021-09281-7
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents