SLGP Header

A Study on the Energy Efficient Path Selection Protocols in Wireless Sensor Network

IJCSEC Front Page

Wireless sensor Network is designed to deal with the intermittent connectivity among mobile nodes due to mobility and it is used to reduce the energy consumption of nodes and to prevent the formation of energy holes. In Order to improve the quality of the Service of the system , we need to obtain best optimal path through the query node however, these benefits are dependent on the path taken by the mobile sink, particularly in delay-sensitive applications, as all sensed data must be collected within a given time constraint. An approach proposed to address this challenge is to form a hybrid moving pattern in which a mobile-sink node only visits rendezvous points (RPs), as opposed to all nodes. Sensor nodes that are not RPs forward their sensed data via multihopping to the nearest RP. The fundamental problem then becomes computing a tour that visits all these RPs within a given delay bound. Identifying the optimal tour, however, is an NP-hard problem. To address this problem, a heuristic called weighted rendezvous planning (WRP) is proposed, whereby each sensor node is assigned a weight corresponding to its hop distance from the tour and the number of data packets that it forwards to the closest RP.
Keywords: Wireless Sensor Network , Energy Management , Path prediction , QOS.
Key issue in wireless Sensor Network (WSN) system design is to minimize the overall system cost (deployment, operation, maintenance and abolishment) and power consumption. Most of the existing WSN systems rely on standard full-fledged transceivers equipped on each sensor node for communication with sinks and each other. However, in most cases, the receiver module of a transceiver is more costly and consumes more energy than the transmitter. Each sensor node has the capability to collect and process data, and to forward any sensed data back to one or more sink nodes via their wireless transceiver in a multihop manner. In addition, it is equipped with a battery, which may be difficult or impractical to replace, given the number of sensor nodes and deployed environment. These constraints have led to intensive research efforts on designing energy-efficient protocols [1]. In multihop communications, nodes that are near a sink tend to become congested as they are responsible for forwarding data from nodes that are farther away. Thus, the closer a sensor node is to a sink, the faster its battery runs out, whereas those farther away may maintain more than 90% of their initial energy [2]. To this end, previous works such as [15] and [16] employ one or more mobile sinks. These mobile sinks survey and collect sensed data directly from sensor nodes and thereby help sensor nodes save energy that otherwise would be consumed by multihop communications. The travelling path of a mobile sink depends on the realtime requirement of data produced by nodes. For example, in hard real-time applications such as a fire-detection system [8], environmental data need to be collected by a mobile sink quickly. Moreover, a mobile-sink node may change its position after a certain period of time and select another data collection/ feasible site. The feasible sites and corresponding sojourn time are dependent on the residual energy of sensor nodes [9]– [11]. In general, limitations such as the maximum number of feasible sites [14], maximum distance between feasible sites, and minimum sojourn time [15] govern the movement of a mobile sink.
In WSNs with a mobile sink, one fundamental problem is to determine how the mobile sink goes about collecting sensed data. One approach is to visit each sensor node to receive sensed data directly [12]. This is essentially the well-known travelling salesman problem (TSP) [16], where the goal is to find the shortest tour that visits all sensor nodes. However, with an increasing number of nodes, this problem becomes intractable and impractical as the resulting tour length is likely to violate the delay bound of applications. To this end, researchers have proposed the use of rendezvous points (RPs) to bound the tour length [17], [18]. This means a subset of sensor nodes are designated as RPs, and non-RP nodes simply forward their data to RPs. A tour is then computed for the set of RPs.As a result, the problem, which is called rendezvous design, becomes selecting the most suitable RPs that minimize energy consumption in multihop communications while meeting a given packet delivery bound. A secondary problem here is to select the set of RPs that result in uniform energy expenditure among sensor nodes to maximize network lifetime.
In this paper, we call this problem the delay-aware energy efficient path (DEETP). We show that the DEETP is an NP hard problem and propose a heuristic method, which is called weighted rendezvous planning (WRP), to determine the tour of a mobile-sink node. In WRP, the sensor nodes with more connections to other nodes and placed farther from the computed tour in terms of hop count are given a higher priority. Thus, this paper is summarized as follows:  We define the problem of finding a set of RPs to be visited by a mobile sink. The objective is to minimize energy consumption by reducing multihop transmissions from sensor nodes to RPs. This also limits the number of RPs such that the resulting tour does not exceed the required deadline of data packets.  We propose WRP, which is a heuristic method that finds a near-optimal traveling tour that minimizes the energy consumption of sensor nodes. WRP assigns a weight to sensor nodes based on the number of data packets that they forward and hop distance from the tour, and selects the sensor nodes with the highest weight.  We mathematically prove that selecting the sensor node that forwards the highest number of data packets and have the longest hop distance from the tour reduces the network energy consumption, as compared with other nodes. Moreover, we show that, in contrast to cluster-based (CB) [17], rendezvous design for variable tracks (RD-VT) [33], and rendezvous planning utility-based greedy (RP-UG) [17] algorithms, WRP is guaranteed to find a tour if the latter exists. • We demonstrate via computer simulation the properties and effectiveness of WRP against the CB [17], RD-VT [18], and RP-UG algorithms [18]. Our results show that WRP achieves 14% more energy savings and 22% better distribution of energy consumption between sensor nodes than the said algorithms. The remainder of this paper is structured as follows. Section II reviews methods. Section III presents energy efficient models of the system. In Section IV, we conclude.


  1. I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Commun. Mag., vol. 40, no. 8, pp. 102–114, Aug. 2002.
  2. J. Lian, K. Naik, and G. B. Agnew, “Data capacity improvement of wireless sensor networks using non-uniform sensor distribution,” Int. J. Distrib. Sens. Netw., vol. 2, no. 2, pp. 121–145, Apr.–Jun. 2006.
  3. J. Li and P. Mohapatra, “An analytical model for the energy hole problem in many-to-one sensor networks,” in Proc. 62nd IEEE Veh. Technol. Conf., Dallas, TX, USA, Sep. 2005, vol. 4, pp. 2721–2725.
  4. J. Luo and J.-P. Hubaux, “Joint mobility and routing for lifetime elongation in wireless sensor networks,” in Proc. IEEE INFOCOM, Miami, FL, USA, Mar. 2005, vol. 3, pp. 1735–1746.
  5. R. C. Shah, S. Roy, S. Jain, and W. Brunette, “Data mules: Modeling and analysis of a three-tier architecture for sparse sensor networks,” Ad Hoc Netw., vol. 1, no. 2/3, pp. 215–233, Sep. 2003.
  6. X. Li, A. Nayak, and I. Stojmenovic, Sink Mobility in Wireless Sensor Networks. Hoboken, NJ, USA: Wiley, 2010, pp. 153–184.
  7. E. Ekici, Y. Gu, and D. Bozdag, “Mobility-based communication in wireless sensor networks,” IEEE Commun. Mag., vol. 44, no. 7, pp. 56–62, Jul. 2006.
  8. S. Jain, R. Shah, W. Brunette, G. Borriello, and S. Roy, “Exploiting mobility for energy efficient data collection in wireless sensor networks,” Mobile Netw. Appl., vol. 11, no. 3, pp. 327–339, Jun. 2006.
  9. I. Chatzigiannakis, A. Kinalis, and S. Nikoletseas, “Sink mobility protocols for data collection in wireless sensor networks,” in Proc. 4th ACM Int. Workshop Mobility Manage. Wireless Access, Terromolinos, Spain, Oct. 2006, pp. 52–59.
  10. I. Chatzigiannakis, A. Kinalis, and S. Nikoletseas, “Efficient data propagation strategies in wireless sensor networks using a single mobile sink,” Comput. Commun., vol. 31, no. 5, pp. 896–914, Mar. 2008.
  11. J. Capella, A. Bonastre, J. Serrano, and R. Ors, “A new robust, energy efficient and scalable wireless sensor networks architecture applied to a wireless fire detection system,” in Proc. Int. Conf. Wireless Netw. Inform. Syst., Shanghai, China, Dec. 2009, pp. 395–398.
  12. Z.Wang, S. Basagni, E. Melachrinoudis, and C. Petrioli, “Exploiting sink mobility for maximizing sensor networks lifetime,” in Proc. 38th Annu. Hawaii Int. Conf. Syst. Sci., Hawaii, USA, Jan. 2005, p. 287a.
  13. S. Basagni, A. Carosi, E. Melachrinoudis, C. Petrioli, and Z. M. Wang, “Controlled sink mobility for prolonging wireless sensor networks lifetime,” Wireless Netw., vol. 14, no. 6, pp. 831–858, Dec. 2008.
  14. Y. Bi, L. Sun, J. Ma, N. Li, I. A. Khan, and C. Chen, “Hums: An autonomous moving strategy for mobile sinks in data-gathering sensor networks,” EURASIP J.Wireless Commun. Netw., vol. 2007, pp. 64574-1– 64574-15, 2007.
  15. Y. Yun and Y. Xia, “Maximizing the lifetime of wireless sensor networks with mobile sink in delay-tolerant applications,” IEEE Trans. Mobile Comput., vol. 9, no. 9, pp. 1308–1318, Sep. 2010.
  16. M. Gatzianas and L. Georgiadis, “A distributed algorithm for maximum lifetime routing in sensor networks with mobile sink,” IEEE Trans. Wireless Commun., vol. 7, no. 3, pp. 984–994, Mar. 2008.
  17. J. Luo, J. Panchard, M. Pirkowski, M. Grossglauser, and J.-P. Hubaux, “Mobiroute: Routing towards a mobile sink for improving lifetime in sensor networks,” in Distributed Computing in Sensor Systems, P. Gibbons, T. Abdelzaher, J. Aspnes, and R. Rao, Eds. Berlin, Germany: Springer- Verlag, 2006, pp. 480–497.
  18. M. Ma and Y. Yang, “Data gathering in wireless sensor networks with mobile collectors,” in Proc. IEEE Int. Symp. Parallel Distrib. Process., Miami, FL, USA, Apr. 2008, pp. 1–9.