Premium
Localization and scheduling protocols for actor‐centric sensor networks
Author(s) -
Das Sajal K.,
Ghidini Giacomo,
Navarra Alfredo,
Pinotti Cristina M.
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21454
Subject(s) - computer science , wireless sensor network , topology (electrical circuits) , scheduling (production processes) , computer network , vertex (graph theory) , upper and lower bounds , distributed computing , graph , mathematical optimization , theoretical computer science , mathematics , combinatorics , mathematical analysis
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. © Wiley Periodicals, Inc. NETWORKS, Vol. 2012.