Localization and Scheduling Protocols for Actor-Centric Sensor Networks

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.