Optimal Deployment of m-Coverage and k-Connectivity Wireless Sensor Networks

Project: Research

View graph of relations



Wireless Sensor Networks (WSNs) are gaining rapid popularity and acceptance today with many important applications. Deployment is a fundamental issue that affects many facets of network operation in WSNs. In many missions today, sensors are deployed deterministically in a planned manner. Instances include airport/ harbor monitoring, governmental areas intruder tracking etc., where sensors are hand-placed at selected locations. Clearly, the success of such missions is tightly contingent on deployment quality. Fundamentally, knowledge of optimal deployment patterns will help avoid ad-hoc deployment (and likely inefficient patterns) by providing sound theoretical bounds. Optimal patterns also have benefits like cost-savings (sensors still cost $100 apiece), minimizing message collisions, better network management etc. Furthermore, study of optimal patterns necessitates tremendous insights into network topology, which will provide a guideline for subsequent extensions of optimal patterns in non-ideal and more practical deployment scenarios.However, the issue of exploring optimal deployment patterns is very hard and far from mature in WSNs. The reason is that this issue falls into the areas of computational geometry and topology, and there are no solid theoretical foundations in both these areas for tackling this issue. The consequence is that existing results so far have only focused on optimal patterns under severe restrictions. For instance, optimal patterns exist for only 1-coverage and 1- connectivity, 2-connectivity and 6-connectivity in WSNs for restricted ratios of communication to sensing ranges. The goal of this project is to comprehensively study this issue. The researchers will study optimal deployment patterns from several perspectives including, optimal patterns to achieve 1-coverage and k-connectivity, and m-coverage (m>1) and kconnectivity; optimal patterns for the above in non-ideal scenarios like non-uniform communication/ sensing ranges, heterogeneity with respect to gateway nodes and deployment field; repairing corrupted deployment patterns by using limited sensor mobility; building a prototype system for testing/ evaluation. The outcomes of this project have important impacts to Hong Kong. There are many important missions (e.g., airports and harbors monitoring, governmental areas intruder tracking etc.) in Hong Kong wherein sensor networks will be deployed deterministically. The results from this project can be significantly leveraged by these missions. Furthermore, the results can also serve as important guidelines for optimally deploying other types of general wireless networks.The project team is confident in completing this project. The team members have extensive experiences in WSNs topology design, algorithms/ protocols design, wireless network test-beds, which are all closely related to this project.


Project number9041350
Grant typeGRF
Effective start/end date1/09/088/09/10