Habib M. Ammari
Skip Abstract Section
Abstract
Coverage is one of the fundamental concepts in the design of wireless sensor networks (WSNs) in the sense that the monitoring quality of a phenomenon depends on the quality of service provided by the sensors in terms of how well a field of interest is covered. It enables the sensors to detect any event that may occur in the field, thus, meeting the application-specific requirements. Several applications require k-coverage, where each point in the field is covered by at least k sensors, which helps increase data availability to ensure better data reliability. Achieving k-coverage of a field of interest becomes a more challenging issue in sparsely deployed WSNs. Though the problem of coverage in WSNs has been well studied in the literature, only little research efforts have been devoted to the case of sparsely deployed WSNs. Thus, in this article, we investigate the problem of k-coverage in sparse WSNs using static and mobile sensors, which do not necessarily have the same communication range, sensing range, and energy supply. Precisely, we propose an optimized, generalized framework for k-coverage in sparsely deployed WSNs, called k-SCHEMES, which exploits sensor heterogeneity and mobility. First, we characterize k-coverage using heterogeneous sensors based on Helly's Theorem. Second, we introduce our energy-efficient four-tier architecture to achieve mobile k-coverage of a region of interest in a field. Third, on top of this architecture, we suggest two data-gathering protocols, called direct data-gathering and forwarding chain-based data-gathering, using the concept of mobile proxy sink. We found that the second data-gathering protocol outperforms the first one. For energy-efficient forwarding, we compute the minimum transmission distance between any pair of consecutive mobile proxy sinks forming the forwarding chain as well as the corresponding optimum number of mobile proxy sinks in this chain. We corroborate our analysis with several simulation results.
- Ai, J. and Abouzeid, A. 2006. Coverage by directional sensors in randomly deployed wireless sensor networks. J. Combinatorial Optim. 11, 1, 21--41.Google Scholar
Cross Ref
- Aloupis, G., Cardinal, J., Collette, S., Langerman, S., Orden, D., and Ramos, P. 2010. Decomposition of multiple coverings into many parts. Discrete Computat. Geometry 44, 3, 706--723. Google ScholarDigital Library
- Ammari, H. M. and Das, S. K. 2012. Centralized and clustered k-coverage protocols for wireless sensor networks. IEEE Trans. Comput. 61, 1, 118--133. Google ScholarDigital Library
- Ammari, H. M. and Giudici, J. 2009. On the connected k-coverage problem in heterogeneous sensor nets: The curse of randomness and heterogeneity. In Proceedings of the International IEEE Conference on Distributed Computing Systems (ICDCS). 265--272. Google ScholarDigital Library
- Bai, X., Kumar, S., Xuan, D., Yun, Z., and Lai, T. H. 2006. Deploying wireless sensors to achieve both coverage and connectivity. In Proceddings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). 131--142. Google ScholarDigital Library
- Bollobás, B. 2006. The Art of Mathematic: Coffee Time in Memphis. Cambridge University Press.Google Scholar
- Bulusu, N., Heidemann, J., and Estrin, D. 2000. GPS-less low cost outdoor localization for very small devices. IEEE Personal Commun. Mag. 7, 5, 28--34.Google ScholarCross Ref
- Burrell, J., Brooke, T., and Beckwith, R. 2004. Vineyard computing: Sensor networks in agricultural production. IEEE Perv. Comput. 3, 1, 38--45. Google ScholarDigital Library
- Cao, G., Kesidis, G., La Porta, T., Yao, B., and Phoha, S. 2006. Purposeful mobility in tactical sensor networks. In Sensor Network Operations, Wiley-IEEE Press, 113.Google Scholar
- Cao, Q., Yan, T., Stankovic, J., and Abdelzaher, T. 2005. Analysis of target detection performance for wireless sensor network. In Proceedings of the IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS). 276--292. Google ScholarDigital Library
- Du, X. and Lin, F. 2005a. Maintaining differentiated coverage in heterogeneous sensor networks. EURASIP J. Wirel. Commun. Netw. 5, 4, 565--572. Google ScholarDigital Library
- Du, X. and Lin, F. 2005b. Improving sensor network performance by deploying mobile sensors. In Proceedings of the International Performance Computing and Communications Conference (IPCCC). 67--71.Google Scholar
- Duarte-Melo, E. J. and Liu, M. 2002. Analysis of energy consumption and lifetime of heterogeneous wireless sensor networks. In Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM). 21--25.Google Scholar
- Gibson, M., Kanade, G., Krohn, E., Pirwani, I. A., and Varadarajan, K. R. 2008. On clustering to minimize the sum of radii. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 819--825. Google ScholarDigital Library
- Guo, W., Liu, Z., and Wu, G. 2003. An energy-balanced transmission scheme for sensor networks. In Proceedings of the ACM International Conference on Embedded Networked Sensor Systems (SenSys). 300--301. Google ScholarDigital Library
- Gupta, H., Zhou, Z., Das, S., and Gu, Q. 2006. Connected sensor cover: Self-organization of sensor networks for efficient query execution. IEEE/ACM Trans. Netw. 14, 1, 55--67. Google ScholarDigital Library
- Heinzelman, W., Chandrakasan, A., and Balakrishnan, H. 2002. An application-specific protocol architecture for wireless microsensor networks. IEEE Trans. Wirel. Commun. 1, 4, 660--670. Google ScholarDigital Library
- Heo, N. and Varshney, P. K. 2005. Energy-efficient deployment of intelligent mobile sensor networks. IEEE Trans. Syst. Man Cybernet. Syst. Humans 35, 1, 78--92. Google ScholarDigital Library
- Huang, C., Tseng, Y., and Wu, H. 2007. Distributed protocols for ensuring both coverage and connectivity of a wireless sensor network. ACM Trans. Sens. Netw. 3, 1, 1--24. Google ScholarDigital Library
- Klein, L. A. 1993. A Boolean algebra approach to multiple sensor voting fusion. IEEE Trans. Aerospace Electron. Syst. 29, 2, 317--327.Google ScholarCross Ref
- Kumar, S., Lai, T., and Balogh, J. 2004. On k-coverage in a mostly sleeping sensor network. In Proceedings of the ACM International Conference on Mobile Computing and Networking (MobiCom). 144--158. Google ScholarDigital Library
- Lazos, L. and Poovendran, R. 2006. Stochastic coverage in heterogeneous sensor networks. ACM Trans. Sens. Netw. 2, 3, 325--358. Google ScholarDigital Library
- Li, X., Wan, P., and Frieder, O. 2003. Coverage in wireless ad-hoc sensor networks. IEEE Trans. Comput. 52, 6, 753--763. Google ScholarDigital Library
- Liu, B., Brass, P., and Dousse, O. 2005. Mobility improves coverage of sensor networks. In Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). 300--308. Google ScholarDigital Library
- Liu, C., Wu, K., Xiao, Y., and Sun, B. 2006. Random coverage with guaranteed connectivity: Joint scheduling for wireless sensor networks. IEEE Trans. Parallel Distrib. Syst. 17, 6, 562--575. Google ScholarDigital Library
- Luo, J. and Hubaux, J.-P. 2005. Joint mobility and routing for lifetime elongation in wireless sensor networks. In Proceedings of the IEEE International Conference on Computer Communication (INFOCOM). 1735--1746.Google Scholar
- Ma, Y., Dalal, S., Alwan, M., and Aylor, J. 2003. ROP: A resource oriented protocol for heterogeneous sensor networks. In Proceedings of the Virginia Tech's Symposium on Wireless Personnel Communications. 59--70.Google Scholar
- Meghanathan, N. 2009. On the connectivity, lifetime and hop count of routes determined using the city section and Manhattan mobility models for vehicular ad hoc networks. In Proceedings of the International Conference on Contemporary Computing (ICCC). 170--181.Google ScholarCross Ref
- Megerian, S., Koushanfar, F., Potkonjak, M., and Srivastava, M. 2005. Worst and best-case coverage in sensor networks. IEEE Trans. Mobile Comput. 4, 1, 84--92. Google ScholarDigital Library
- Mhatre, V., Rosenberg, C., Kofman, D., Mazumdar, R., and Shroff, N. 2005. A minimum cost heterogeneous sensor network with a lifetime constraint. IEEE Trans. Mobile Comput. 4, 1, 4--15. Google ScholarDigital Library
- Nicules, D. and Nath, B. 2003. Ad-hoc positioning system (APS) using AoA. In Proceedings of the IEEE International Conference on Computer Communication (INFOCOM). 1734--1743.Google Scholar
- Olariu, S. and Stojmenovic, I. 2006. Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting. In Proceedings of the IEEE International Conference on Computer Communication (INFOCOM). 1--12.Google Scholar
- Pach, J. 1986. Covering the plane with convex polygons. Discrete Computat. Geometry 1, 1, 73--81. Google ScholarDigital Library
- Pach, J. and Toth, G. 2009. Decomposition of multiple coverings into many parts. Computat. Geometry Theory Appli. 42, 2, 127--133. Google ScholarDigital Library
- Rao, R. and Kesidis, G. 2004. Purposeful mobility for relaying and surveillance in mobile ad hoc sensor networks. IEEE Trans. Mobile Comput. 3, 3, 225--232. Google ScholarDigital Library
- Shah, R. C., Roy, S., Jain, S., and Brunette, W. 2003. Data MULEs: Modeling a three-tier architecture for sparse sensor networks. In Proceedings of the IEEE International Workshop on Sensor Networks Protocols and Applications (ISNPA). 30--41.Google Scholar
- Shakkottai, S., Srikant, R., and Shroff, N. 2003. Unreliable sensor grids: Coverage, connectivity and diameter. In Proceedings of the IEEE International Conference on Computer Communication (INFOCOM). 1073--1083.Google Scholar
- Sohrabi, K., Merill, W., Elson, J., Girod, L., Newberg, F., and Kaiser, W. 2004. Methods for scalable self-assembly of ad hoc wireless sensor networks. IEEE Trans. Mobile Comput. 3, 4, 317--331. Google ScholarDigital Library
- Sun, T., Chen, L., Han, C., and Gerla, M. 2005. Reliable sensor networks for planet exploration. In Proceedings of the IEEE International Conference on Networking, Sensing and Control (ICNSC). 816--821.Google Scholar
- Wang, G., Cao, G., and La Porta, T. 2004a. Movement-assisted sensor deployment. In Proceedings of the IEEE International Conference on Computer Communication (INFOCOM). 2469--2479.Google Scholar
- Wang, G., Cao, G., and La Porta, T. 2004b. Proxy-based sensor deployment for mobile sensor networks. In Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS). 493--502.Google Scholar
- Wang, G., Cao, G., Porta, T. L., and Zhang, W. 2005. Sensor relocation in mobile sensor networks. In Proceedings of the IEEE International Conference on Computer Communication (INFOCOM). 2302--2312.Google Scholar
- Wang, Y.-C., Hu, C.-C., and Tseng, Y.-C. 2008. Efficient placement and dispatch of sensors in a wireless sensor network. IEEE Trans. Mobile Comput. 7, 2, 262--274. Google ScholarDigital Library
- Wang, Y.-C. and Tseng, Y.-C. 2008. Distributed deployment schemes for mobile wireless sensor networks to ensure multi-level coverage. IEEE Trans. Parallel Distrib. Syst. 19, 9, 1280--1294. Google ScholarDigital Library
- Wang, Y., Wang, X., Agrawal, D. P., and Minai, A. A. 2006. Impact of heterogeneity on coverage and broadcast reachability in wireless sensor networks. In Proceedings of the IEEE International Conference on Computer Communications and Networks (ICCCN). 63--67.Google Scholar
- Wu, J. and Yang, S. 2007. Optimal movement-assisted sensor deployment and its extensions in wireless sensor networks. Simulation Model. Pract. Theory 15, 4, 383--399.Google ScholarCross Ref
- Wu, J. and Yang, S. 2005. SMART: A scan-based movement-assisted sensor deployment method in wireless sensor networks. In Proceedings of the IEEE International Conference on Computer Communication (INFOCOM). 2313--2324.Google Scholar
- Xing, G., Wang, X., Zhang, Y., Lu, C., Pless, R., and Gill, C. 2005. Integrated coverage and connectivity configuration for energy conservation in sensor networks. ACM Trans. Sens. Netw. 1, 1, 36--72. Google ScholarDigital Library
- Yang, S. and Cardei, M. 2007. Movement-assisted sensor redeployment scheme for network lifetime increase. In Proceedings of the ACM International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM). 13--20. Google ScholarDigital Library
- Yang, S., Dai, F., Cardei, M., and Wu, J. 2006. On connected multiple point coverage in wireless sensor networks. Int. J. Wirel. Inf. Netw. 13, 4, 289--301.Google ScholarCross Ref
- Yarvis, M., Kushalnagar, N., Singh, H., Rangarajan, A., Liu, Y., and Singh, S. 2005. Exploiting heterogeneity in sensor networks. In Proceedings of the IEEE International Conference on Computer Communication (INFOCOM). 2, 878--890.Google Scholar
- Ye, F., Zhong, G., Cheng, J., Lu, S., and Zhang, L. 2003. PEAS. A robust energy conserving protocol for long-lived sensor networks. In Proceedings of the International IEEE Conference on Distributed Computing Systems (ICDCS). 28--37. Google ScholarDigital Library
- Zhang, H. and Hou, J. 2005. Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc Sen. Wirel. Netw. 1, 1--2, 89--124.Google Scholar
- Zou, Y. and Chakrabarty, K. 2005. A distributed coverage- and connectivity-centric technique for selecting active nodes in wireless sensor networks. IEEE Trans. Comput. 54, 8, 978--991. Google ScholarDigital Library
Index Terms
- Joint k-coverage and data gathering in sparsely deployed sensor networks -- Impact of purposeful mobility and heterogeneity
Recommendations
Fault tolerance measures for large-scale wireless sensor networks
Connectivity, primarily a graph-theoretic concept, helps define the fault tolerance of wireless sensor networks (WSNs) in the sense that it enables the sensors to communicate with each other so their sensed data can reach the sink. On the other hand, ...
Centralized and Clustered k-Coverage Protocols for Wireless Sensor Networks
Sensing coverage is an essential functionality of wireless sensor networks (WSNs). However, it is also well known that coverage alone in WSNs is not sufficient, and hence network connectivity should also be considered for the correct operation of WSNs. ...
Connectivity preserving localized coverage algorithm for area monitoring using wireless sensor networks
Efficient network coverage and connectivity are the requisites for most Wireless Sensor Network (WSN) deployments, particularly those concerned with area monitoring. Due to the resource constraints of the sensor nodes, redundancy of coverage area must ...
Comments