Efficient End to End Routing using RSSI & Simulated Annealing

Efficient End to End Routing using RSSI & Simulated Annealing

Revti Kaura Sachin Majithia

M.Tech (IT) Asst. Prof., IT Department Chandigarh Engineering College, Landran Chandigarh Engineering College, Landran

Abstract

To choose or design energy efficient and reliable routing protocols for mobility centric Wireless Sensor Networks (WSN) applications is a great challenge. It is ideal to realize end to end routing in wireless sensor networks because packets can be delivered by only maintaining a small set of neighbours information regardless of network size. A fundamental problem in WSN is localization i.e. determination of geographical locations of sensor nodes. This paper addresses the problem of location discovery of the nodes in WSN. In it, existing cluster-based routing protocol for mobile sensor networks called LEACH-M is used. Received signal strength indication (RSSI) measurements are used to estimate the distance of an anchor node to a mobile node. Simulated Annealing (SA) is a generic probabilistic algorithm for the global optimization problem. We evaluate our approaches through experiments, showing that routing performance is improved in terms of routing success ratio and routing cost.

1. Introduction

   The evolutions in sensor technology and wireless communication have led to the development of wire-less sensor networks (WSNs). A WSN comprises of a large number of tiny sensor nodes, which are low-cost and low power. Numerous sensors are ad hoc deployed in the interested area. These sensors collect physical in-formation, process it and forward the local information to the sink nodes. Therefore the back-ends can obtain global views according to the information provided by the sensors [1, 2].

   Clustering-based routing protocols are considered as more energy efficient since in these protocols, cluster head (CH) produce limited useful information from a large amount of raw sensed data by member nodes in a cluster and transmit this precise useful information to the base station (BS) of a network that consumes less energy [1, 4]. Most clustering protocols of WSN in the literature are designed for static sensor nodes and thus, not suitable for WSN applications that require mobile sensor nodes such for habitat monitoring,

   wildlife monitoring, and heath. Low Energy Adaptive Clustering Protocol (LEACH) [2] is a standard clustering protocol of WSN. LEACH is enhanced as LEACHMobile [3]

   Determining location of nodes i.e. localization is a fundamental problem for applications in WSN with large number of nodes. Location information in WSNs enables efficient routing, power saving in applications like target tracking, locating the source of the data etc. Manual configuration of locations is not feasible for large-scale network with mobile nodes. Providing each node with localization hardware such as global positioning system (GPS) receiver is not a valid option for such tiny devices as GPS is expensive in terms of cost and energy consumption. A more reasonable solution to the localization problem is to allow some nodes called seeds/beacons to have their location information available at all times, and allow other nodes to inform their locations by exchanging messages with beacons. [6]

   Localization algorithms can be divided into two categories: range-based or fine-grained and range-free or coarse-grained approach [7]. Range-based approaches normally require accurate distance or angle measurements to compute the location of unknown node. Each of the range- based technique such as Angle of Arrival (AoA), Time of Arrival (ToA), Time Difference of Arrival (TDoA) needs an additional stuff such as antennas or accurately synchronized clocks. The only exception from these requirements is a Received Signal Strength Indicator (RSSI) technique. RSSI is considered as the simplest and cheapest method amongst the wireless distance estimation techniques, since it does not require additional hardware for distance measurements and is unlikely to significantly impact local power consumption, sensor size and thus cost.

   Simulated annealing is a generic probalistic algorithm for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. SA unlike conventional greedy routing does not force a message to monotonically get closer to the

   destination at each hop. This algorithm is inspired by optimization theory.

   In this paper, we formulate the problem of local minima & low quality routes. Cost & complexity is also reduced by reducing the amount of anchors. We propose a localization technique by means of which a sensor node can determine its location with enhanced accuracy by listening wireless transmissions from three or more beacons. The proposed method is based on RSSI technique that does not require any additional complexity in construction of the sensor nodes [6]. Then, the Simulated Annealing (SA) based heuristic is proposed to solve the optimization problem [4, 5].

   The rest of this paper is organized as follows. Related work is reviewed in section 2. The Problem description is then described in section 3. The System model is described in section 4. Furthermore, the Computational results are discussed in section 5, and Conclusions & Future work is presented in section 6 & 7 respectively. Finally References are mentioned in section 8.

2. Related Work

   The enhancement to LEACH to support mobility is addressed in LEACH-Mobile, in short LEACH-M [18]. The basic idea in LEACH-M is to confirm whether a mobile sensor node is able to communicate with a specific cluster head or not. This is implemented by transmitting a message, which requests for data transmission back to mobile sensor node from cluster head within a time slot allocated in TDMA schedule of a wireless sensor cluster. If the mobile sensor node does not receive the data transmission from cluster head within an allocated time slot according to TDMA schedule, it sends a join-request message at next TDMA time slot allocated. Then it decides the cluster to which it will belong for this moment by receiving cluster join-ack messages back from specific cluster heads. The LEACH-M protocol achieves definite improvement in data transfer success rates as mobile nodes increase compared to the non-mobility centric LEACH protocol.

   Simulated annealing (SA) [11], [12] is commonly said to be the first algorithm extending local search methods with an explicit strategy to escape from local optima. The main idea is to allow moves resulting in solutions of worse quality than the current solution in order to escape from local optima. The probability of doing such a move is decreased during the search process. Despite of being proposed in 1983, SA is still object of further studies, tool tackling many optimization problems, and component of other algorithms [13], [14]. Precisely, its outstanding role in the metaheuristic field encourages further studies to obtain more effective SA.

   A sensor network containing many sensors is supposed and each sensor has limited and un-replaceable energy. As each node has various duties, a node's wrong performance

   leads to energy waste and its omission from the network structure. This paper introduces a vigorous algorithm to place sensors to cover maximum areas of network with the lowest cost. This suggested algorithm runs based on simulated annealing (SA) and it can work on networks in which sensors are organized randomly. Since this algorithm analyses sensors' status regularly it can be taken as a dynamic algorithm. The simulation results idicate that proposed algorithm can organize the best areas of networks with numerous sensors through the lowest possible processing, and it significantly enhances the network's lifetime. It also guarantees that during execution procedure, the most possible coverage occurs using the selected sensors. [10]

   RSSI is available during a packet reception with no additional hardware, no impact on energy consumption or throughput. Moreover, this metric seems intuitive: stronger is the received signal, closer is the transmitter and weaker is the received signal, further is the transmitter. RSSI is also used in several standards to determine when the amount of radio energy in the channel is below a certain threshold at which point the node is clear to send. These reasons make RSSI- based techniques very attractive. As a result, they have been widely investigated and the literature on the RSSI is quite huge. A survey on this topic is clearly not the aim of this work. A more complete overview can be found in [8]. The experimental results obtained in this work provide an insight to the feasibility of using RSSI measurements in estimating the location of a target sensor.

3. Problem Description

   Greedy forwarding has been successfully employed by geographic routing, which assumes that a packet can be moved closer to the destination in the network topology if it is forwarded geographically closer to the destination in the physical space. This assumption, however, may lead packets to the local minimum where no neighbours of the sender are closer to the destination or low quality routes that comprise long distance hops of low packet reception ratio.

   Geographic Routing requires nodes location information. Although a number of localization algorithms have been proposed to infer nodes locations with a few GPS- enabled anchors, accurate localization is still subject to errors leading to route failures. In addition, greedy forwarding based on local information cannot ensure global optimum and packets might never reach the desired destination. [9]

4. System Model

   We are working on mobile centric Wireless Sensor Network. It is ideal to realize end to end routing in wireless sensor networks because packets can be delivered by only

   maintaining a small set of neighbours information regardless of network size. Leach-M routing protocol is used to support the mobile nodes in mobile centric WSN. To overcome the problem of localization of nodes, RSSI based localization technique is used. For this purpose, Sensor nodes are distributed randomly. We consider that there are three nodes which are already localized and act as beacons. The beacons know their locations either by GPS or by some other means. Finally, for the global optimization, Simulated Annealing is used. Unlike conventional greedy routing, it does not force a message to monotonically get closer to the destination at each hop. This algorithm is inspired by optimization theory. Each step of it attempts to replace the current solution by a random solution. The simulator used for the above purpose is NS-2.

   1. Objective

      The objective of this work is to propose a low-overhead, simplest and cheapest method amongst the wireless distance estimation techniques by means of which nodes in wireless sensor network can compute their locations. We also aim at solving the problem of local minima low quality routes. We also want to show that routing performance is improved in terms of routing success ratio and routing cost.

   2. Routing Protocol for mobile centric WSN

      The enhancement to LEACH to support mobility is addressed in LEACH-Mobile, in short LEACH-M [18]. The basic idea in LEACH-M is to confirm whether a mobile sensor node is able to communicate with a specific cluster head or not. This is implemented by transmitting a message, which requests for data transmission back to mobile sensor node from cluster head within a time slot allocated in TDMA schedule of a wireless sensor cluster. If the mobile sensor node does not receive the data transmission from cluster head within an allocated time slot according to TDMA schedule, it sends a join-request message at next TDMA time slot allocated. Then it decides the cluster to which it will belong for this moment by receiving cluster join-ack messages back from specific cluster heads. The LEACH-M protocol achieves definite improvement in data transfer success rates as mobile nodes increase compared to the non-mobility centric LEACH protocol.

   3. Range Estimation

      Under ideal conditions, the RSSI value could be used to estimate the distance between the transmitting and receiving nodes. The power received by an antenna (Pr) placed at a distance d from a transmitting antenna with a known amount of transmitted power Pt is given by the Friis transmission equation [16].

      Where Pt and Pr are the transmission and reception power antenna respectively in dBm, Gt and Gr are the antenna gains of the transmitting and receiving antennas respectively,

      is the wavelength, and D is the distance between the antennas. However, studies [3, 16] have recently revealed that most of localization protocols based on RSSI, once deployed in real platforms, have worse behavior than what predicted by simulations. Above equation is an ideal case for a source point and the signal often decays at a faster or slower rate. Practically, its hard to determine antenna gains and a simplified form of the relation between distance and receive power is often used:

      Pr(D) = Pr1 K.log10(D)

      Where Pr1 is the received power in dBm at one meter, K the loss parameter and D the distance between the transmitter and receiver. The values of Pr1 and K are generally determined empirically

   4. Localization

      As mentioned in the system model, there are three beacons present in the network area. A beacon initiates the process by sending its neighbors a message containing its location. Once the message is received by the neighboring nodes of the beacon, to start with, the neighboring nodes store the message and measure the Received Signal Strength (RSS). The other beacons back-off by random time-interval and one by one transmit message. When the beacons finish broadcasting, a set of nodes in the network have received broadcast message from at least three beacons. This set of nodes performs two steps for localization. In the first step, each node calculates its estimated distance from beacons using the RSSI method [6]. In the second step, each node uses trilateration procedure [3] [4] to combine the estimated distances from all the beacons and beacon locations to calculate its own location.

   5. RSSI and Trilateration Method

      In RSSI method, on receiving the beacon message, the neighbouring nodes of the beacon estimate distance from the beacon measuring the received signal strength (RSS) of the broadcast signal. Whenever a node receives broadcast signal from at least three beacons it estimates distances from each of the beacons. Once the distances of the beacons are estimated, the node uses trilateration method to derive its own location. In trilateration method, location of a node is uniquely determined based on its distance from at least three beacons and the locations of the beacons using the trigonometric laws.

   6. Simulated Annealing

      The Simulated Annealing (SA) optimization [7] is based on the physical process of annealing in metallurgy. Unlike conventional greedy routing, it does not force a message to monotonically get closer to the destination at each hop. This algorithm is inspired by optimization theory. It starts with a user given solution, then evaluates it and performs a small modification on the solution. This new candidate solution is evaluated and if its better than the previous, SA accepts it and assumes it as the current solution. If it is not better than the previous, there will be a probability of this new worst solution to be accepted based on the cost of each solution and the presen temperature in the system. The mathematical expression is:

      Where A is the probability of accepting the worst solution, c(N) is the cost of the new solution, c(P) is the cost of the present solution and t is the temperature.

      The SA-based algorithm is a stochastic process. Computing time for the algorithm is relative to the selection of the cooling schedule, the desired solution quality, and the optimization problem itself. Hence, as the size of the problem increases, the time complexity of the problem will become increasingly irrelevant [17].

5. Results

   Fig.5.1. shows the relationship between the routing failure ratio and the anchor set size in the C shape network topology. This figure shows that a small number of anchors is insufficient to represent the network topology and certain number of anchors (more than 30 in this configuration) are required to achieve a relatively low routing failure ratio.

   Fig.5.1. Shows the relationship between the routing failure ratio and the anchor set size

   Fig.5.2. represents a graph between route failure ratio & node failure ratio. For each end-to-end packet delivery, certain percentage of nodes is randomly selected to turn off. We vary the percentage of failed nodes from 5 to 20 percent to investigate the resilience of our proposed work to node failures. We found that node failure ratio was decreased in our work, thus showing better results.

   Fig.5.2. Represents a graph between route failure ratio & node failure ratio.

6. Conclusion

   In this paper, a SA-based algorithm is proposed to design an energy efficient sensor deployment problem. Simulated Annealing has solved the problem of global optimization. RSSI, used for Localization, is cost effective as it doesnt require any additional hardware. By using RSSI for localization & Simulated Annealing for optimization we evaluate our approaches through both simulations and experiments, showing that routing performance is improved in terms of routing success ratio and routing cost.

7. Future Work

   RSSI involves evolutionary computing which may increase the amount of computation. RSSI-based localization in real environment and using standard sensors is not enough accurate. Thus, our future work should focus on these problems.

8. References

1. P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, Routing with Guaranteed Delivery in Ad Hoc Wireless Networks, ACM Wireless Networks, vol. 7, no. 6, pp. 609-616, 2001.

2. B. Karp and H.T. Kung, GPSR: Greedy Perimeter Stateless Routing for Wireless Networks, Proc. MobiCom, 2000.

3. Z. Zhong and T. He, Achieving Range-Free Localization beyond Connectivity, Proc. ACM Conf. Embedded Networked

   Sensor Systems (SenSys), 2009.

4. D.S.J.D. Couto, D. Aguayo, J. Bicket, and R. Morris, A High- Throughput Path Metric for Multi-Hop Wireless Routing, Proc. MobiCom, pp. 134-146, 2003.

5. Y.-J. Kim, R. Govindan, B. Karp, and S. Shenker, Geographic Routing Made Practical, Proc. Conf. Symp. Networked Systems Design (NSDI), vol. 2, pp. 217-230, 2005.

6. Al Alawi,R., RSSI based location estimation in wireless sensors networks, Dept. of Electr. & Electron. Eng., Univ. of Bahrain, Isa Town, Bahrain, 2011

7. M. Rudafshani and S. Datta, Localization in Wireless Sensor Networks, Proc. of IPSN, pp. 51-60, 2007.

8. G. Mao, B. Fidan, and B. D. Anderson. Wireless sensor network localization techniques. Computer Networks, 51(10):2529 2553, 2007.

9. Pei Huang, Chen Wang, Li Xiao; 2011 Improving End-to-End Routing Performance of Greedy Forwarding in Sensor Networks, Dept. of Computer. Sci. & Eng., Michigan State Univ., East Lansing, MI, USA

10. Mappar, M.; Rahmani, A.M.; Ashtari, A.H., 2009; A New Approach for Sensor Scheduling in Wireless Sensor Networks Using Simulated Annealing, Dept. of Comput. Islamic, Azad Univ. of Masjed Soleyman, Masjed Soleyman, Iran

11. S. Kirkpatrick, C. Gelatt Jr, and M. Vecchi, Optimization by simulated annealing, Sci., vol. 220, no. 4598, pp. 671680, 1983.

12. E. Aarts and J. Korst, Simulated Annealing and Boltzmann Machines. John Wiley & Sons, 1989.

13. D. Henderson, S. H. Jacobson, and A. W. Jacobson, The theory and practice of simulated annealing, in Handbook of Metaheuristics.

    Kluwer Academic Publishers Group, 2003, pp. 287319.

14. P. Salamon, P. Sibani, and R. Frost, Facts, Conjectures and Improvements for Simulated Annealing, ser. Monographs on Mathematical

    Modeling and Computation. SIAM, 2002.

15. M. Vossiek, L. Wiebking, P. Gulden, J. Wieghardt, C. Hoffmann, and P. Heide, Wireless local positioning, IEEE Microwave Magazine, vol. 4, no. 4, pp. 7786, 2003.

16. Kraus and Fleisch, Electromagnetics, 5th Ed., McGraw-Hill, 1999.

17. Y.-J. Kim, R. Govindan, B. Karp, and S. Shenker, Geographic Routing Made Practical, Proc. Conf. Symp. Networked Systems Design and Implementation (NSDI), vol. 2, pp. 217-230, 2005.

18. Do-Seong Kim, Yeong-Jee Chung, Self-Organization Routing Protocol Supporting Mobile Nodes for Wireless Sensor Network, Proceedings of the First International Multi-Symposiums on Computer and Computational Sciences (IMSCCS'06), 2006

19. Chagas, Stephan H ; 2012 Genetic Algorithms and Simulated Annealing optimization methods in wireless sensor networks localization using artificial neural networks, UFSM PPGI, Santa Maria, Brazil

20. Heurtefeux, K.; Valois, F., 2012 Is RSSI a Good Choice for Localization in Wireless Sensor Network?, Advanced Information Networking and Applications (AINA), Verimag, Grenoble,France.