Distributed Algorithms for Lifetime of Wireless Sensor Networks Based on Dependencies Among Cover Sets
We present a new set of distributed algorithms for scheduling sensors to enhance the total lifetime of a wireless sensor network. These algorithms are based on constructing minimal cover sets each consisting of one or more sensors which can collectively c
- PDF / 315,970 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 2 Downloads / 185 Views
1 Introduction Wireless sensor networks (WSNs) are emerging as a key enabling technology for applications domains such as military, homeland security, and environment [7]. For example, in typical security surveillance or environmental monitoring scenarios, tiny low-cost radio-enabled sensors can be deployed in large numbers over a difficult or hostile terrain. Then, they configure themselves into a network to collectively sense and route data to gateway nodes. Interested readers are referred to [1] [7] for detailed background, applications and challenges of WSNs. The sensors, by design, have limited battery. Therefore, they must conserve power while communicating, sensing, and computing. One key challenge is to utilize the network effectively to maximize the duration of time while all the targets (or alternatively certain area [9]) can be continuously monitored. This duration is called the lifetime of the network, which is the concern of this paper. Only a subset of sensors usually need to be in “sense” or “on” mode at any given time to cover all the targets (henceforth called “covers” – See Section 2 for a formal definition), while others can go into power conserving “sleep” or “off” mode. Therefore, an ideal sensesleep schedule would choose appropriate covers at various intervals to maximize the lifetime. Thus, at its heart, this is an NP-complete problem [6] [8]. S. Aluru et al. (Eds.): HiPC 2007, LNCS 4873, pp. 381–392, 2007. © Springer-Verlag Berlin Heidelberg 2007
382
S.K. Prasad and A. Dhawan
Both centralized and distributed heuristics have been proposed for finding the longest lifetime schedule. The premise of centralized algorithms, such a those based on linear programming [2] [5], is that, given the locations of sensors and targets, the lifetime scheduling algorithm can be executed offline at the gateway node or elsewhere and then the sense-sleep schedule can be communicated to the sensors. Thus, the premise of global network information is both an advantage yielding better lifetime and a liability due to the associated communication overheads and loss of distributed robustness. The existing distributed algorithms typically work iteratively in rounds of reshuffles of predetermined duration. At the beginning of each reshuffle round, each sensor negotiates with its neighboring sensors to decide on its sense-sleep status such that all its neighboring targets are covered by the sensor itself or one of its neighbors. The limitations of existing algorithms are their simple greedy approaches, lacking enough insight into the problem structure. Section 5 compares and contrasts some of the distributed algorithms against ours, even showing how they can be formulated using our overall framework. Our contributions: Although globally there is exponential number of possible covers making the problem intractable, the number of local covers, those minimal subsets of neighboring sensors covering nearby targets, is usually small. This opens up the problem to individual sensors distributively constructing the local cover
Data Loading...
