On the robustness of grid-based deployment in wireless sensor networks

ABSTRACT

Grid-based sensor deployment is an effective and efficient practice for provisioning wireless sensor networks. Previous work has addressed grid-based deployment of sensors in order to guarantee sensing coverage under the assumption that each device can be placed exactly at the grid vertices. However, in reality, the accuracy of device placement may be subject to various errors, which are shown to impair the sensing coverage. To overcome the negative impacts of these errors, the grid resolution and the number of devices to be deployed should be re-evaluated. In this paper, two deployment errors are identified, namely, misalignment and random errors. We derive the minimum number of sensors required by a robust grid-based sensor deployment assuming that the errors are bounded. This research shows that when designing a realistic large-scale grid-based sensor deployment, errors in device placement must be taken into account.

REFERENCES

• 1: Edoardo S. Biagioni , Galen Sasaki, Wireless Sensor Placement For Reliable and Efficient Data Collection, Proceedings of the 36th Annual Hawaii International Conference on System Sciences (HICSS'03) - Track 5, p.127.2, January 06-09, 2003
• 2: Krishnendu Chakrabarty , S. Sitharama Iyengar , Hairong Qi , Eungchun Cho, Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks, IEEE Transactions on Computers, v.51 n.12, p.1448-1453, December 2002 [doi>10.1109/TC.2002.1146711]
• 3: Yuzhen Liu , Weifa Liang, Approximate Coverage in Wireless Sensor Networks, Proceedings of the The IEEE Conference on Local Computer Networks 30th Anniversary, p.68-75, November 15-17, 2005 [doi>10.1109/LCN.2005.32]
• 4: Tian He , Sudha Krishnamurthy , John A. Stankovic , Tarek Abdelzaher , Liqian Luo , Radu Stoleru , Ting Yan , Lin Gu , Jonathan Hui , Bruce Krogh, Energy-efficient surveillance system using wireless sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990096]
• 5: Xiaorui Wang , Guoliang Xing , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration in wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958496]
• 6: Q. Wang, K. Xu, G. Takahara and H. Hassanein, "Locally Optimal Relay Node Placement in Heterogeneous Wireless Sensor Networks", IEEE Globecom'05, 2005.
• 7: Seapahn Megerian , Farinaz Koushanfar , Miodrag Potkonjak , Mani B. Srivastava, Worst and Best-Case Coverage in Sensor Networks, IEEE Transactions on Mobile Computing, v.4 n.1, p.84-92, January 2005 [doi>10.1109/TMC.2005.15]
• 8: G. Wang, G. Cao and T. L. Porta, "Movement-Assisted Sensor Deployment", IEEE Infocom'04, Vol.4, pp. 2469--2479, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Performance

Keywords:
coverage, grid-based deployment, misalignment, random error, robustness, wireless sensor network