IEATH: Improved Energy Aware and Two Hop Multipath Routing Protocol in Wireless Sensor Networks

Автор: S. Saqaeeyan, M. Roshanzadeh

Журнал: International Journal of Computer Network and Information Security(IJCNIS) @ijcnis

Статья в выпуске: 5 vol.4, 2012 года.

Бесплатный доступ

Wireless sensor networks in terms of energy sources are limited. Furthermore due to this type of network infrastructure wireless communications and channel errors not possible to reach the correct packet to the destination exists; hence the proposing algorithms to improve the quality of service in these networks and sending packets are very important. In this paper we proposed a reliable and energy aware packet delivery mechanism to ensure quality of service in wireless sensor networks. In our proposed algorithm to ensure that a packet of information sent to the destination, the multi-path Forwarding method is used; So that several copies of an information packet via separate routes are sent to the destination, also routing decisions in this way occurs by considering the remaining energy in the neighborhood of nodes that are located in two hop of sender node. Simulation results show that the rate of release of data packets reduced in this way and thus the reliability of packet is increased, also the energy efficiency of sensor nodes effectively improved. Therefore this algorithm increase overall lifetime in wireless sensor networks.

Еще

Wireless Sensor Networks, Reliability, multi-path routing, Energy, Lifetime

Короткий адрес: https://sciup.org/15011082

IDR: 15011082

Текст научной статьи IEATH: Improved Energy Aware and Two Hop Multipath Routing Protocol in Wireless Sensor Networks

Published Online June 2012 in MECS

A sensor network consists of many sensor nodes that for collect information from the environment are distributed widely in the environment. Sensor networks to their wide applications in various fields and also, the network has given a special place. These networks have ability to identify, classify, process and transmit data obtained from the sensing parameters within the network. Each sensor node in the network consists of three components: the sensor component which is used to sense the environment, the processing component which performs the local computations on the sensed data, and the communication component which is responsible for sharing the sensed data with the neighboring sensor nodes. The sensor component senses the data in the environment. The processing component processes the sensed data. The communication component sends the aggregated data to the sink node. A sensor network consists of different types of sensors such as seismic, thermal, visual, and infrared. They are presented in various areas such as: life sciences, medical care and the vital signs, military affairs and development, and in general wherever it is needed to measure the physical quantity [1], [2]. A greater number of sensors allows sensing over larger geographical regions with greater accuracy.

Necessarily, the place of the sensor nodes is not predetermined and specified. These feature can provides dropping them in dangerous or inaccessible places. This means that the sensor network protocols and algorithms should be a self authorization. Another unique feature of sensor networks, sensor nodes are capable of cooperation and coordination. Each sensor node contains a processor and instead of sending all the raw data to the center or to a node that is responsible for processing, it first in a series of processes and the information obtained is simple performs semi-processed and then send the data. In designing of wireless sensor networks should be given to the key parameters of these networks; Many of these parameters for optimal design together and should not be a compromise between them. Quality of Service, end-to-end delay and network lifetime in these networks are important parameters [3]. For example, in a scenario which sensors have been distributed in areas inaccessible and dangerous, it is impossible to replace or recharge their batteries [4], [5]. Therefore it is necessary to consider the useful life of the network that all the sensors are to collect process and transmit data. Additionally, protocols should be fully aware of the delay between the source and destination.

In most applications, sensor nodes are constrained in energy supply and communication bandwidth. Thus, innovative techniques to eliminate energy inefficiencies that shorten the lifetime of the network and efficient use of the limited bandwidth are highly required. Such constraints combined with a typical deployment of large number of sensor nodes pose many challenges to the design and management of WSNs and necessitate energyawareness at all layers of the networking protocol stack.

For example, at the network layer, it is highly desirable to find methods for energy-efficient route discovery and relaying of data from the sensor nodes to the sink so that the lifetime of the network is maximized.

Finally, the data from sensor networks and general emergency should be reported as soon as possible. The main objective in the design of many critical applications is desired raising the possibility of arriving packets to the destination. And the result of compromise between these parameters is necessary in various applications. Given the diversity of applications in sensor networks and their different needs, different ways to carry packets are available or deliver packets on time is their most desired and increase the chances of getting packets to the destination is emphasized. For example, in a network that uses the geographic routing and sensor nodes are not moving or sedentary, it is necessary to place the packets in a packet is sent periodically to the neighbors. These packets can be sent with a small percentage of error and lower reliability. If a packet contains important information about the temperature of the environment or an unexpected event in the range, it must achieve greater high-speed and probability be sent. Maintain quality of services for traffic with the characteristics listed in above, Because of the high-scale and dynamic network topology changes due to movement of the sensor nodes and add nodes and downtime caused. In addition to being inherently unreliable wireless channels, is highly problematic Depending on the type of information should therefore be specified. It is decided based on the content and requirements in routing the packet towards the destination. Also due to this type of communication network infrastructure and considering communicate the nodes via wireless radio signals and exist the noise in the channel, there is a possibility that errors occur on transmitted data nodes from source to destination. On networks that have a high number of jumps between the source and destination probability of receive a packet by the destination is very low. Considering the important nodes have sending data on some cases such as report of a fire on the forest applying methods to ensure reliability of data is critical. To ensure reliability of data transmission some methods have been proposed:

  •    Acknowledging method to collect data and retransmit corrupted packets

  •    Using encrypted channels with data redundancy

  •    Redundancy packets: sending multiple copies of a packet through a safe route

  •    Path redundancy: sending the same data packets through multiple paths

Considering the need to sending more data, to improve the reliability of sending data it should be noted that redundancy on transmitted data can increase energy consumption on sensor nodes and thus reduces the lifetime of sensor networks. Hence an efficient protocol is a protocol that in addition to ensuring the reliability of sending data, it is also optimal in terms of energy consumption.

The remainder of the paper is arranged as follows. Section-II provide Related works and background about multipath routing protocol for data sending in Wireless Sensor Networks and also it demonstrate ReInForm algorithm. The details of the proposed algorithm namely IEATH has been discussed in section-III. In section-IV, Experimental Results are shown, in this section first ReInForm protocol was implemented in Network Simulator and then the new proposed model namely IEATH is presented. Finally, in the section-V conclusions are presented.

  • II.    Related works

Routing in WSNs is very challenging due to the inherent characteristics that distinguish these networks from other wireless networks like mobile ad hoc networks or cellular networks. To minimize energy consumption, routing techniques proposed in the literature for WSNs employ some well-known routing tactics as well as tactics special to WSNs, such as data aggregation and in-network processing, clustering, different node role assignment, and data-centric methods. Almost all of the routing protocols can be classified according to the network structure as flit, hierarchical, or location-based. Furthermore, these protocols can be classified into multipath-based, query-based, negotiationbased, quality of service (QoS)-based, and coherentbased depending on the protocol operation. In flat networks all nodes play the same role, while hierarchical protocols aim to cluster the nodes so that cluster heads can do some aggregation and reduction of data in order to save energy. Location-based protocols utilize position information to relay the data to the desired regions rather than the whole network. The last category includes routing approaches based on protocol operation, which vary according to the approach used in the protocol.

The fault tolerance of a protocol is measured by the likelihood that an alternate path exists between a source and a destination when the primary path fails. This can be increased by maintaining multiple paths between the source and destination at the expense of increased energy consumption and traffic generation. These alternate paths are kept alive by sending periodic messages. Hence, network reliability can be increased at the expense of increased overhead in maintaining the alternate paths. Many algorithms to improve the quality of service parameters in wireless sensor networks are presented that some of them have considered only one parameter. Presented algorithm in the ReInForm [6] increased reliability through multiple paths. In single path routing, the source sends the data in a single route but in case of multi-path, source sensor finds many path to the sink and distribute the data evenly among the paths. In this algorithm, the number of required routes to send copies of packets is calculated, associated with error in each link and the number of steps and the reliability. The main idea of this algorithm, in order to obtain reliable data delivery, that way multiple copies of each packet is sent through several paths from source to destination [7], [8], [9], [10]. In this way, if any error in information on some routes, there is likely to reach the correct packets from other routes. In Fig.1 Multi-Path sending is shown.

Any numbers of paths selected for data transmission from source to destination are more the data reliability to be more. Which is much more choice of routes, more nodes are selected for data transmission. This is causes more power loss in the network and thus reducing the overall lifetime of the network. It should be a compromise between reliability requirements and number of selected routes.

ReInForm provides desired reliability in packet delivery in presence of any channel error rate by sending multiple copies of a single packet along multiple paths. Hence it relies heavily on the existence of multiple paths from source to sink. Only if sufficiently large numbers of paths exist from source to sink without too much deviation in the number of hops from the optimal, the multipath approach would succeed. When the number of paths between any two nodes is not sufficient for providing the reliability required, there may be more one copy of a packet per path. The reliability that can be achieved using multipath forwarding depends on the expected number of such paths. The number of edge disjoint paths gives a good bound for the above because number of paths would be at least as large the number of disjoint paths. In ReInForm algorithm on generating a packet, the source node determines the importance of the information it contains and decides the desired reliability r s for it. It also knows the local channel error e s and its hop distance from sink h s . Using these values, the source computes the number of paths (or equivalently, the number of copies of the packet to be sent) P required for delivering the packet at desired reliability to the sink as:

P ( rs, es, hs ) =

log( 1 - rs ) log(1 - (1 - es ) hs )

The source S is at a distance hs from the sink. The neighborhood set of the source is divided into 3 subsets Hs-, Hs0 and Hs+ which contain neighbors at distance hs –1 , hs and hs + 1 respectively. The source selects one of the members of Hs- set at random, and designates it the next hop. Since the graph is assumed to be connected, there is at least one node in set Hs-. This ensures that at least one member to-wards the sink forwards. Choosing a random next hop helps in load balancing. In ReInForm algorithm, the remaining energy of nodes not in terms of routing decisions, hence it may be selected nodes to send packets which have remaining low energy and do unable to send the packet. On the other hand, this makes some of the nodes more quickly lose its energy. To resolve this problem, we have presented a new algorithm that can resolve this weakness. This algorithm is described in detail in the next section.

In [11], multipath routing was used to enhance the reliability of WSNs. The proposed scheme is useful for delivering data in unreliable environments. It is known that network reliability can be increased by providing several paths from source to destination and sending the same packet on each path. However, using this technique, traffic will increase significantly. Hence, there is a tradeoff between the amount of traffic and the reliability of the network. This tradeoff is studied in [11] using a redundancy function that is dependent on the multipath degree and failing probabilities of the available paths. The idea is to split the original data packet into subpackets and then send each sub-packet through one of the available multipath. It has been found that even if some of these sub-packets are lost, the original message can still be reconstructed. According to their algorithm, it has also been found that for a given maximum node failure probability, using a higher multipath degree than a certain optimal value will increase the total probability of failure. Directed diffusion [12] is a good candidate for robust multipath routing and delivery. Based on the directed diffusion paradigm, a multipath routing scheme that finds several partially disjoint paths is studied in [13] (alternate routes are not node disjoint, i.e., routes are partially overlapped). It has been found that the use of multipath routing provides a viable alternative for energy-efficient recovery from failures in WSNs. The motivation for using these braided paths is to keep the cost of maintaining the multi paths low. The costs of alternate paths are comparable to the primary path because they tend to be much closer to the primary path.

One of the main challenges in the design of routing protocols for WSNs is energy efficiency due to the scarce energy resources of sensors. The energy consumption of the sensors is dominated by data transmission and reception. Therefore, routing protocols designed for WSNs should be as energy efficient as possible to prolong the lifetime of individual sensors, and hence the network lifetime. In the sensor nodes energy supply is a battery and these sensors not ability to recharge or replace the batteries. Hence, the proposing method will be able to consume less energy with maintain existing quality of services is very important in enhancing the lifetime of sensor nodes and ultimately increase the overall lifetime of wireless sensor networks. Furthermore, this will reduce the cost of wireless sensor networks.

In EARQ algorithm [14], a node estimate consumed energy, delay and reliability of each path to the sink only by using the information in nodes that are in its neighborhood. Then, it calculates the probability of selecting a route by using these estimates. When is required to forward a packet, this algorithm to send a packet randomly selects the next node. Probability of choosing a route with lower cost is more, because the cost and the probability of selecting a node are also negative correlation. In this algorithm, in order to delivery of realtime packets only routes are selected which have ability delivery of packets in the required time. Also to access the required reliability, this algorithm sends duplicate packets through additional routes. EARQ takes advantages of the location information to form one or multiple routing pipes from the source to the destination. Multiple routes might be used simultaneously in EARQ to improve the reliability. EARQ can greatly improve the energy efficiency, also minimizing the cost reliability and time factor it improve the energy in a great extent. EARQ provides a simple approximation of the minimum delay, given the density of sensor nodes and radio range. The minimum delay is important because a deadline shorter than the minimum delay will results in numerous packets missing the deadline. Many of existing protocols in under water sensor networks are lack of its energy consumption.

In the presented routing algorithm in [15] by using improved techniques in forwarding data packets, this algorithm has improved the efficiency of consumption energy of sensor nodes and quality of service. This algorithm focus on operational and architectural challenges of handling QoS routing traffic in sensor networks and proposed a new mechanism for QoS based routing protocol by applying different techniques simultaneously. In this algorithm network is static and nodes are distributed in random format. So, there exists only one base station or gateway which is deployed at a fixed place in the center of the area.

The authors in [16] proposed an algorithm that routes data through a path whose nodes have the largest residual energy. The path is changed whenever a better path is discovered. The primary path will be used until its energy falls below the energy of the backup path, at which time the backup path is used. Using this approach, the nodes in the primary path will not deplete their energy resources through continual use of the same route, hence achieving longer life. However, the path switching cost was not quantified in the article. The authors of [17] proposed the use of a set of suboptimal paths occasionally to increase the lifetime of the network. These paths are chosen by means of a probability that is depends on how low the energy consumption of each path. The path with the largest residual energy when used to route data in a network may be very energy-expensive too, so there is a tradeoff between minimizing the total power consumed and the residual energy of the network. The authors in [18] proposed an algorithm in which the residual energy of the route is relaxed a bit in order to select a more energy efficient path.

  • III.    IEATH: Improved Energy Aware and Two Hop Multipath Routing Protocol

In sensor networks, location is often more important than a specific node ID. In this paper, we assume that each node knows about the location and amount of its remaining energy and nodes are aware of the location and energy amount of nodes that are in their radio range through a special packet called a " hello packet " that will be send periodically. Nodes by using GPS [19] or other determining methods with very little cost can find its location and GPS help the sensor nodes to know their current locations. Each sensor node, will notice the moment of its energy to neighboring nodes by riding on the ACK messages. So sensors are aware of their left over energy and also the location information and remaining energy of their neighbors.

  • A.    Route selection based on remaining energy of nodes

In our proposed algorithm, try that the routing decisions racing forward to select nodes according to the energy parameters of the remaining nodes. So that, in addition to considering the reliability of nodes, the remaining amount can also be considered. For this purpose, the nodes are ordered based on remaining energy and between the available nodes, one node is selected for the racing forward, have might more energy remaining. This action causes will decrease the traffic load of nodes that have a lower energy and therefore increase their lifetime. This increase causing high performance wireless sensor networks and increasing their global lifetime.

  • B.    Routing decisions based on information nodes are located in the two jump

In our proposed method, the routing decision is done according to nodes that are located at a distance with two jump sender node. Access to information for node that are located at a distance with two jump to sender node, each node periodically calls from neighbors that their routing table information including their neighbors they are sent to the requesting node.

With access to the neighbor`s table sender node in addition to the information nodes that are in one jump themselves, the information will be available to the nodes that are located in two jumps. To reduce the overhead caused of this information, nodes only request the required information. In our algorithm only will be ask information about the remaining energy of nodes. Also, to reduce the traffic caused by sending information packets, these packets with the piggyback method on the acknowledgement packets will be sent to the applicant node. Efficiency of this method is due to the fact that whatever the value awareness sender node is more extensive than its neighbor nodes , a route that is selected for the forward chosen can be more accurate and more efficient and this causes that prevent of sending to the routes have nodes with lower energy. For example when where node are located in a jump have the same conditions in terms of remaining energy, our algorithm compared with each other nodes are located in the next jump in this case it select a path be better off in terms of energy.

  • C.    Enhancing the reliability of data transmission by using a hybrid method

In our proposed algorithm to enhance the reliability of data used a combination of methods. First, we refer to weakness of ReInForm algorithm and then we express the proposed solution to resolve it. In the ReInForm algorithm, if the number of nodes that are in the neighborhood of sender node be less than the number of nodes required by the obtained by (1), sender node is forced to send packets to fewer nodes. Send fewer copies of packets can reduce the reliability of packet. This operation in some cases will cause the packets could not to reach the destination.

In our proposed method to solve the problem lack of nodes so that the if the number of neighboring nodes is less than the needed nodes, sender nodes will act to send a duplicate copies of packets through the same routes. For example if for the achieve reliability requirements, be required to send 4 copies of the packet but there are only 3 nodes in the neighborhood of sender node, sender node first sends a copy of the packet to each node's neighborhood; Now the fourth copy of the packet will send via one of 3 available nodes. With this action we have been able to maintain the required reliability. Considering that sending more copies of packet through a node, will cause more energy consumption in this node. Sender node among the 3 neighborhood nodes, one node selects to sending duplicate packet that have more remaining energy than other nodes.

  • IV.    Experimental Results

For simulation proposed algorithm (IEATH) we have used the NS2 simulator [20]. To prove the superior performance of the proposed method, the simulation results are compared with the ReInForm algorithm.we have done the simulation With Considering the same conditions for both methods according to specifications in Table (1). We do the experiment for 200 seconds first with ReInForm and then with the proposed method IEATH. We compare the two aspects together, the results obtained from the simulation. First, the remaining energy of nodes, and second, the number of data packets that do not reach to the destination during the implementation. The results are shown in the next section.

table i. simulation settings.

Band Width

12.8 Kbps

Mac Layer

802.11

Number of Nodes

200

Node Placement

Random

Radio Range

50 m

Terrain

500m * 500m

The test lasts for 200 seconds and the events are produced by three separate sources. Respite of generated packets from first and second sources is 1.75 second and probability of achieving them is 0.65. Respite of generated packets from first and second sources is 1.5 second and probability of achieving them is 0.75. With these conditions the simulation is running. Routing packets is performed first with ReInForm protocol and then with the presented protocol IEATH.

  • A.    Results of simulation in the field of energy consumption

In this section simulation results in the field of energy consumption are examined in sensor nodes. A node is considered dead when it runs out of energy and loses the ability to send or receive packets. The results are shown in Fig. 2. As shown in the diagram, in ReInForm algorithm, sensor nodes respectively started to lose their energy of time 21 and in the second 100 about 40 nodes lost their energy and they are not able to sending data and work in the network. On the other hand, in IEATH protocol to almost any of the sensors in the 50 seconds has not lost its energy. But after the 110th seconds in a short time interval many numbers of sensors lose their energy. As was predicted this is due to the equal distribution of load between the nodes and the network. This cause the nodes with an almost equal proportion lose their energy.

  • B.    Results of simulation in the field of Dropped packets

In this section, we examine the results of simulating in the field of the release of data packets; occur the packet loss could have several reasons including: errors in data, loss of energy nodes, the deadline to send packets and other items. However, the simulations performed we evaluate the results Fig. 3 shows the results of the simulation. With evaluating results, the conclusion reached that until 60 seconds for both algorithms are almost equal rate of release packet. But after this time, release rate of packets in the ReInForm algorithm will start to increase; the reason for this increase is loss of energy nodes after this time. However, in the IEATH algorithm release rate of the packets was almost identical until the 160 seconds. After this time rate of release packet start to increase. Similar in ReInForm, the increased release of this is due to end the life of sensor nodes. Moreover, the residual energy of nodes on the release rate of packets. The new routing decisions reduce the rate of release packets that sends more copies of the packets through the routes with more energy. This causes to increase reliability in the wireless sensor networks.

Figure 3. Number of Dropped Packets.

  • V.    Conclusions

In this paper, we provide an optimized routing algorithm for wireless sensor networks in terms of energy and reliability. In our proposed algorithm, routing decisions are based on the remaining energy of nodes. Also, by using a combined approach we improved the reliability of data sending and decrease rate of dropped packets. The results of simulation shown that our proposed algorithm effectively distributed traffic load in network between the nodes and the overall lifetime of wireless sensor networks has increased. Moreover, the presented algorithm by increase reliability in data sending reduces in the number of release packets that are sent to the destination.

Acknowledgment

This paper derived from research project "Proposing an optimum routing algorithm for improving QoS in wireless sensor network".

Done in Sama technical and vocational training college Islamic Azad University, Shushtar Branch, Shushtar, Iran.

Список литературы IEATH: Improved Energy Aware and Two Hop Multipath Routing Protocol in Wireless Sensor Networks

  • J. Haartsen, M. Naghshineh, J. Inouye, O. Joeressen, and W.Allen:Bluetooth:Vision, goals, and architecture. Mobile Computing and Communications Review, vol.2, no.4,(1998038–45) Conference on Architectural Support for Programming Languages and Operating Systems, (2000) 93–104.
  • J. Hill, R. Szewczyk, A.Woo, S. Hollar, D. Culler, and K. Pister: System architecture directions for networked sensors. 9th ACMInternational Conference on Architectural Support for Programming Languages and Operating Systems, (2000) 93–104.
  • Xia, F, "Review: QoS Challenges and Opportunities in Wireless Sensor/Actuator Networks " Sensors, vol. 8, pp. 1099-1110, 2008.
  • S. R. Madden et al., "TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks," in Proceedings of OSDI, Dec. 2002.
  • R. Min et al., "Energy-centric enabling technologies for wireless sensor networks," in Proceedings of IEEE Wireless Communications, Aug. 2002, pp. 28-39.
  • B. Deb, S. Bhatnagar, and B. Nath, "ReInForm": Reliable Information Forwarding Using Multiple Paths in Sensor Networks," Proc. IEEE Int'l Conf. Local Computer Networks, pp. 406-415, 2003.
  • D. Ganesan, R. Govindan, S. Shenker and D. Estrin Highly Resilient, Energy Efficient Multipath Routing in Wireless Sensor Networks. Mobile Computing and Communications Review (MC2R) Volume 1, (2002).
  • M. Marina and S.Das On Demand Multipath Distance Vector Routing in Ad Hoc Networks IEEE International Conference on Network Protocols (ICNP), (2001).
  • A. Nasipuri and S.R. Das On Demand Multipath Routing for Mobile Ad Hoc Networks 8th International Conference on Computer Communications and Networks (IC3N). Boston (1999).On Demand Multipath Routing for Mobile Ad Hoc Networks 4th European Personal Mobile Communication Conference (EPMCC), Vienna (2001).
  • S. Dulman et al., "Trade-Off between Traffic Overhead and Reliability in Multipath Routing for Wireless Sensor Networks," WCNC Wksp., New Orleans, LA, Mar. 2003.
  • C. Intanagonwiwat, R. Govindan, and D. Estrin, "Directed Diffusion: a Scalable and Robust Communication Paradigm for Sensor Networks," Proc. ACM Mobi- Com 2000, Boston, MA, 2000, pp. 56–67.
  • D. Ganesan et al., "Highly Resilient, Energy-Efficient Multipath Routing in Wireless Sensor Networks," ACM SIGMOBILE Mobile Comp. Commun. Rev., vol. 5, no. 4, 2001, pp. 11–25.
  • EARQ, 2011, SRIMATHI.C: Energy Aware Routing For Real-Time Sensor Networks. International Journal of Engineering Science and Technology (IJEST) Vol. 3 No. 1 Jan 2011.
  • N, Zaman: Different Techniques Towards Enhancing Wireless Sensor Network Routing Energy Efficiency and Quality of Service. World Applied Sciences Journal 13(4):798-805, 2011.
  • J.-H. Chang and L. Tassiulas, "Maximum LifetimeRouting in Wireless Sensor Networks," Proc. Adv. Telecommun. and Info. Distrib. Research Prog., College Park, MD, Mar. 2000.
  • C. Rahul and J. Rabaey, "Energy Aware Routing for Low Energy Ad Hoc Sensor Networks," IEEEWCNC,vol. 1, Mar. 17–21, 2002, Orlando, FL, pp. 350–55.
  • Q. Li, J. Aslam and D. Rus, "Hierarchical Power-Aware Routing in Sensor Networks," Proc. DIMACS Wksp. Pervasive Net., May, 2001.
  • N. Bulusu, J. Heidemann, and D. Estrin, "GPS-less Low Cost Outdoor Localization for Very Small Devices", IEEE Personal Communication Magazine, vol. 7, no. 5, Oct. 2000, pp. 28-34
  • Marc Greis' Tutorial for the UCB/LBNL/VINT Network Simulator "NS" http://www.isi.edu/nsnam/ns/tutorial/
Еще
Статья научная