×

Localization and scheduling protocols for actor-centric sensor networks. (English) Zbl 1242.68012

Summary: We propose novel localization and routing protocols in an actor-centric wireless sensor network consisting of an actor node and a large number of energy-constrained sensors operating under \(L\) different periodic sleep-awake schedules. Specifically, we propose a semidistributed localization algorithm in which a small subset of sensors extracts their positions in polar coordinates based on the messages received from the actor, and subsequently localizes (also in polar coordinates) the remaining sensors. By modeling the deployed sensors as a two-dimensional Poisson point process and applying well-known results from the coupon collector’s problem and Chernoff bounds, we analytically derive and also validate, by simulation, the sensor density required to localize all sensors in the network with high probability. The actor-centric network can be modeled by a cluster adjacency graph \(G\) with the help of the already localized polar coordinates that logically partition the network into concentric coronas (around the actor), each subdivided in a varying number of clusters (of almost the same area). To avoid intercluster collisions in \(G\), sensors in different clusters transmit on different channels. A lower bound on the number of channels required to schedule the transmissions without collisions is obtained by solving a distance-2 vertex coloring problem on \(G\). Optimal and quasioptimal fully distributed algorithms are provided to determine the channel assigned to each cluster in constant time. Finally, we apply these results to develop a geographic routing protocol: the messages generated from the sensors in a given cluster are routed toward the actor through the unique shortest path of \(G\) that starts from the node associated with the cluster and goes up to the corona where the actor resides. In each cluster, to avoid redundant retransmissions toward the actor, we select \(L\) leaders, one for each periodic sleep-awake schedule.

MSC:

68M12 Network protocols
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text: DOI

References:

[1] Akyildiz, Wireless sensor and actor networks: Research challenges, Ad Hoc Netw 2 pp 351– (2004) · doi:10.1016/j.adhoc.2004.04.003
[2] Arora, A line in the sand: A wireless sensor network for target detection, classification, and tracking, Comput Netw 46 pp 605– (2004) · doi:10.1016/j.comnet.2004.06.007
[3] Barsi, Asynchronous corona training protocols in wireless sensor and actor networks, IEEE Trans Parallel Distributed Syst 20 pp 1216– (2009) · doi:10.1109/TPDS.2008.223
[4] Barsi, Efficient location training protocols for heterogeneous sensor and actor networks, IEEE Trans Mobile Comput 10 pp 377– (2011) · doi:10.1109/TMC.2010.168
[5] Bertossi, Efficient corona training protocols for sensor networks, Theor Comput Sci 402 pp 2– (2008) · Zbl 1156.68307 · doi:10.1016/j.tcs.2008.03.007
[6] Cao, Towards optimal sleep scheduling in sensor networks for rare-event detection, Proc 4th Int Symp Inform Process Sensor Netw pp 20– (2005)
[7] Di Francesco, Data collection in wireless sensor networks with mobile elements: A survey 8 (2011)
[8] S. Du A. K. Saha D. B. Johnson RMAC: A routing-enhanced duty-cycle MAC protocol for wireless sensor networks 2007 1478 1486
[9] Frey, Geographic and energy-aware routing in sensor networks, Chapter 12 pp 381– (2005)
[10] G. Ghidini C. M. Pinotti S. K. Das A semi-distributed localization protocol for wireless sensor and actor networks 2010 438 443
[11] Kingman, Poisson processes (1993)
[12] Kleinberg, Algorithm design (2006)
[13] B. Liu D. Towsley A study of the coverage of large-scale sensor networks 2004 475 483
[14] Lu, Delay efficient sleep scheduling in wireless sensor networks pp 2470– (2005)
[15] Mainwaring, Wireless sensor networks for habitat monitoring (2002) · doi:10.1145/570738.570751
[16] Motwani, Randomized algorithms (1995) · doi:10.1017/CBO9780511814075
[17] Nakano, Uniform leader election protocols for radio networks, IEEE Trans Parallel Distributed Syst 13 pp 516– (2002) · doi:10.1109/TPDS.2002.1003864
[18] Navarra, Cooperative training for high density sensor and actor networks, IEEE J Selected Areas Commun 28 pp 753– (2010) · doi:10.1109/JSAC.2010.100612
[19] Shah, Data MULEs: Modeling and analysis of a three-tier architecture for sparse sensor networks, Ad Hoc Netw 1 pp 215– (2003) · doi:10.1016/S1570-8705(03)00003-9
[20] Wadaa, Training a wireless sensor network, Mobile Netw Appl 10 pp 151– (2005) · doi:10.1023/B:MONE.0000048552.15853.c2
[21] Wang, Duty-cycle-aware broadcast in wireless sensor networks pp 468– (2009)
[22] Xu, A wireless sensor network for structural monitoring pp 13– (2004)
[23] Yick, Wireless sensor network survey, Comput Netw 52 pp 2292– (2008) · doi:10.1016/j.comnet.2008.04.002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.