Improved Multi-Path and Multi-Speed Routing Protocol in Wireless Sensor Networks

Published Online March 2012 in MECS                                     and Computer Science

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. 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].

Necessarily, the place of the sensor nodes is not predetermined and specified. This feature can provides drop 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 the design 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 to large and dangerous, it is impossible to replace or recharge their batteries. 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.

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.

It provides quality of service that separates the two distinct areas, namely timeliness and reliability. So that their packets the best combination in terms of their needs the timeliness and reliability choose from among various options. Routing in a network is done without the knowledge of network topology and the establishment of a route. When a sensor node is the sign packet provides to report the incident to the control center, the content of the sensor data are appropriate the end-to-end deadline for the source node and the possibility of achieving and towards the destination and sends packets with MMSpeed protocol.

MMSpeed protocol using the specified deadline and the geographic distance to destination [4], depending on the speed of a suitable substrate, can be classified. The speed of the layer, the nodes that they speed toward the target layer is larger than the guaranteed rate. It will select a few suitable nodes. So that the total probability of reaching their potential and achieve more than it needed to be closed. After determining the next steps and the number of nodes that the packet should receive they will be added to all packets. The local decisions to select the layer and the speed of the receiving node may not be suitable for the next step; Because of local estimates for the next model of the network nodes have no information that has been used. Thus a dynamic balance of the compensation rate, the possible errors in the form of local decision-making during the global packet is correct. This practice is increases the likelihood of achieving the end-to-end deadline. However, all the packets will not necessarily reach their destination to reach the destination the desired speed in the specified deadline the packets may be forcibly abandoned and unable ever to the destination. In addition, the MAC layer may fail after a few times that you try to transmit packets to drop. Increase high error rate of wireless channels and packet loss probability. Therefore, to ensure the imminent arrival of a certain number of packets to the destination another method is needed. Several routes to the final destination in a high density network there may not be the shortest path. These routes are accepted until the deadline specified in order to deliver the packets.

In some cases, the modification time and avoid the crowded paths of the network longer than the shorter routes are preferable. MMSpeed protocol to ensure reliability of the sending packets uses of the multi path routes. Any number of routes that carry the packets is more likely to reach the final destination, even drop the packets conk wireless nodes is also more trial and error. Therefore, controlling the number of posts based on the amount of credit desired routes, allowing the separation of the reliability of services provided. Each node or multiple nodes that are likely to achieve the desired match for packet generation are selected based on local error estimates and geographical distance of each step is done to adjacent neighbors. Despite the high efficiency protocol MMSpeed, the protocol decisions about choosing the appropriate sensor nodes for the next step is without knowledge of the amount of energy remaining in the adjacent sensors.

The result may be selected routes pass through certain nodes and adjusting the time and energy is not restored. In addition, sometimes all the energy of a node in a particular situation may make it difficult for network. For example, nodes that are adjacent to the control center or sink, if the workload is not distributed fairly, may soon lose their energy. And the other hand, failure to sink the entire network will likely result in disconnect and efficiency and greatly reduces the network lifetime.

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

• II.    R elated works

Many algorithms to improve the quality of service parameters in wireless sensor networks is presented that some of them have considered only one parameter. Presented algorithm in the reference ReinForm [5] increased reliability through multiple 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 [6], [7], [8], [9]. 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.

Figure 1. Multi Path Sending.

Any number of paths selected for data transmission from source to destination is more 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 directions as accepts.

Speed [10] is only intended to delay the algorithm parameters. The algorithm for real-time data, the delay to all its neighbors can hold in the table and sending the packets, one of its neighboring nodes are considered for the post. In that case, neighboring nodes are unable to provide the time needed for the packet, the packet will be removed to prevent overcrowding and traffic and a feedback data is sent to the source.

The main objective of the protocol is guarantees end-to-end delay for real-time packets in wireless sensor networks. This protocol for directing the packet toward the destination uses the method based on the geographical location of nodes without the knowledge of network topology. Each node is aware of the location of nearby neighbors and the delay to their ability to prevent overcrowding and the estimated end-to-end delay of the delay steps are possible. This protocol uses the distance to the sink and the delay between adjacent nodes, depending on the speed towards the target can be evaluated and sensor node sends the packet toward the low rate of speed that is greater than the requested packet. So, if will be sent with a higher rate of speed toward the destination, the requested rate can be guaranteed in the entire network.

The MMSPEED routing protocol is designed with two important goals:

One, localized packet routing decision without global network state update or a priori path setup, and two providing differentiated QoS options in isolated timeliness and reliability domains. For the localized packet routing without end-to-end path setup and maintenance, geographic routing mechanism based on location awareness is used. Each sensor node is assumed to be aware of its geographical location. This location information can be exchanged with immediate neighbors with “periodic location update packets”. Thus, each node is aware of its immediate neighbors within its radio range and their locations. Using the neighbor locations, each node can locally make per packet routing decision such that packets progress geographically towards their final destinations. If each node relays the packet to a neighbor closer to the destination area, the packet can eventually be delivered to the destination without global topology information. For on-time delivery of packets with different end-to-end deadlines, MMSPEED provides multiple delivery speed options that are guaranteed network-widely. For this, the idea of SPEED protocol which can guarantee a single network-wide speed was used. If every node i in the entire network can relay a packet to a neighbor node j whose progress speed toward destination k , is higher than the pre-specified speed lower bound SetSpeed , then the SetSpeed can be uniformly guaranteed all over the network. In SPEED protocol, each node i maintains delay estimation to each neighbor j calculates its progress speed:

Speed^ = (dlstLd- dlst^/detoy^ (1)

and forwards a packet to a neighbor j whose progress speed is higher than SetSpeed . However, nodes in a congested area may not be able to find any node with progress speed higher than SetSpeed . Those nodes start reducing workload by probabilistically dropping packets in order to retain at least one forwarding node whose progress speed is higher than SetSpeed . This approach compromises reliability for assuring networkwide uniform speed SetSpeed with a high probability. Along with packet dropping, nodes also issue so-called “backpressure packets” to reduce the incoming packet traffic from other neighboring nodes.

MMSPEED protocol exploits such inherent redundancies to probabilistically guarantee the required end-to-end reliability level (end-to-end reaching probability) of a packet. The more paths we use to deliver a packet, the higher is the probability that the packet reaches its final destination, despite packet drops, node failures, and errors on wireless links. Thus, by controlling the number of forwarding paths depending on the required reliability level, service differentiation in the reliability domain can be provided [4]. The challenging task is to devise local decision mechanisms to compute and identify forwarding paths to meet the packets end-to-end attainability requirement. To address this problem, a combination of multipath forwarding based on local estimation and dynamic compensation is used. Each node locally determines multiple forwarding nodes to meet the required reaching probability based on local error estimations and geographic hop distances to immediate neighbors. More specifically, each node i can maintain the recent average of packet loss rate, to each immediate neighbor node j . The packet loss includes both intentional packet drops for congestion control and errors on the wireless channel. The estimation of packet loss rate is also supported by MAC layer loss estimation. By using node i can locally estimate the end-to-end attainability of a packet from node i to the final destination d via a neighbor node j as follows:

jufl = (1- €_Ц)(1- а^-^^ы!        (2)

Where is hop count estimation from node j to the final destination d.

Note that this local estimation equation is based on two assumptions:

• 1)    Packet loss rate in each of the following hops will be similar to the local loss rate of the current hop.

• 2)    For each following hops, the geographic progress to the destination will be similar to the current progress.

From the end-to-end attainability estimation via a single neighbor node, the number of forwarding nodes is determined to satisfy the end-to-end attainability requirement of a packet. More specifically, the total reaching probability TRP is initially set to zero. Whenever we add one forwarding node j , the TRP is updated as follows:

TRP = 1-(1- TRF           (3)

Forwarding nodes are added until TRP becomes larger than. Once the set of required forwarding nodes are determined, the packet is delivered to them using the MAC multicast service. However, the local decision on multiple forwarding node selection may turn out to be incorrect in the following nodes because local estimations are used to model the remaining part of the network about which the local node does not have any information. To address this problem, dynamic compensation in the reliability domain is used. By combining aforementioned timeliness and reliability guarantee mechanisms, MMSPEED protocol can serve various packets with different timeliness and reliability requirements.

In the sensor nodes energy supply is a battery and this 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 [11], 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 reference [12] 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.

• III.    I mproved M ulti P ath and M ulti S peed R outing P rotocol

In multi path sending methods for access to required reliability, the same copies of a packet send through multiple routes. If the number of nodes that are in neighbors of sender node are less than needed paths to achieve the requirements reliability Packets are sent with less reliability. This may be suffer the error and unable to send to destination. In proposed protocol IMMSpeed, for the lack of neighboring nodes that are used to achieve the required reliability, a complementary approach is presented.

In the proposed method, if the numbers of needed neighbors were not enough, other copy of the packet sent through repetitive paths. So that, more copies of packets are sent via the same route. For example, if for reach reliability to send a packet, 4 path is needed but now neighbors of nodes are only 3 nodes to achieve the required reliability, a copy of the duplicate packets are sent through a third node, this method is cause increase required reliability. In such circumstances, to load balancing in the network different methods can be used: One method is, select nodes randomly to send more copies, this method distribute load traffic in network. Another method that presented in our proposed protocol, nodes are selected based on their remaining energy.

In this way, a node with have more energy remaining than the other neighbors can be selected to send more copies of packets. Therefore, with considering the remaining energy in routing decisions, efficiently the network load distributed between other nodes and it will increase network longevity. So by using the new method, greatly improves the reliability required that the receiving nodes are selected based on their energy level, the traffic load is distributed among the sensors and consequently their energy can be adjusted. This will ultimately lead to increased life expectancy network. Another usage of this method is for increase forward speed together with ensuring needed reliability.

As was said before, there are several nodes in the neighborhood around each node which are divided into three categories: The first category is the number of nodes that are up to their destination less than a jump to the sender node. The second category have equal number of jumps with the sender node and the third category, have number the higher jump to destination than the node to source. It is desirable that for candidate selected node forward, chosen from among the nodes that are located in the first category; if the number of nodes in the first category were not enough, remaining nodes are selected of the second and third categories. Obviously, second and third categories have more hops to the sink, which may cause longer delays. Thus, when the delay with the reliability is required, the nodes are selected from first category and packets to be sent repeatedly. When choosing an appropriate node for the next step, may be the energy of all sensor nodes to be same with the nodes are located in the radio range of transmitters.

In this state, nodes are classified as priority descending speed respectively towards their destination. Node with the maximum speed towards the destination is the first node that is eligible to be selected for sending this packet. In the IMMSpeed protocol to select a node for the next step the energy level of nodes in the priority candidates are expected to increase the average lifetime of sensors. However, when energy is the same in sensors routing is done based on their speed. Thus the shorter route chosen to send packets toward the destination which is also conserves energy.

In addition to balancing the load among the sensors and increase lifetime average in the network, there is always the possibility to choose suitable paths for sending packets. Rate of lost packets almost remains same to all life of network. However, in the routing with MMSpeed protocol, in first is very high the packet transmission rate and in a short time the rate is decreases because available Sensors in the optimal paths gradually lose their energy and packets are done routing through other routes.

In critical cases, may be unable to find suitable any node for next step and packets are dropped and therefore, increased the drop rate of packets. In the conditions that there are two sensors for sending packet to the same destination and one of them has a higher forward speed while there is less energy than other sensor, in such a case, MMSpeed protocol select the Low-energy nodes for the next jump. That this choice may lead to loss energy of the sensor and therefore, all next packets may be added to achieve the destination through the longer routes. In other special conditions, when not too much difference between the energy of the selected node to the next hop, But they have to be much difference between their forward speed towards destination, if the current packet require a high forward speed, the IMMSpeed protocol, select the node that has a higher speed for the next step. This causes the in addition, network load balancing and increase the lifetime of sensors, also end to end packet delay requirements are provided. Simulations have been performed prove that presented ideas.

• IV.    E xperimental R esults

In this section, first MMSpeed protocol was implemented in Network Simulator NS2 [13] and then the new proposed model for routing in wireless sensor network namely IMMSpeed is presented. General settings of the simulation can be found in Table 1.

table i . simulation settings .

Band Width	12.8Kbps
Mac layer	802.11
Number of Nodes	192
Node placement	Uniform
Radio range	140
Terrain	650m*600m

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 MMSpeed protocol and then with the presented protocol IMMSpeed.

• 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 the MMSpeed algorithm, sensor nodes respectively started to lose their energy of time 34 and in the second 100 about 30 nodes lost their energy and they are not able to sending data and work in the network. On the other hand, in IMMSpeed protocol until 126 seconds almost none of the sensors is not lost his energy. But after the 160 seconds in a short time interval many number of them nearly 50 percent of all 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.

Figure 2. Number of Dead Nodes.

• 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 MMSpeed algorithm will start to increase; the reason for this increase is loss of energy nodes after this time. However, in the IMMSpeed algorithm release rate of the packets was almost identical until the 160 seconds. After this time rate of release packet start to increase. Similar MMSpeed, 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.

Time (sec)

Figure 3. Number of Dropped Packets.

• C.    Results of simulation in the field of Packets delay

In this section, the results of the simulation are evaluated in the field of packets delay. These results are shown in two graphs on Fig. 4 and Fig. 5. The simulation results show that packet delay in IMMSpeed algorithm compared with the MMSpeed algorithm slightly increased and packets during take more time to destination. This increase in delay is due to the choice of routes that in addition to considering the speed, the remaining nodes also consider the remaining energy of nodes. In such conditions, it is possible the selected paths will incur more delays. However, the conditions considered in the IMMSpeed algorithm, in the case if not too much difference between the residual energy of nodes, packets are sent through the paths that have more speed. Fig. 4, compared delays resulting in the some packets together in a time interval. As is shown in the Fig. 4, packets delay in IMMSpeed is more than MMSpeed. However, this delay in the most cases will not lead to loss of deadline of the packets and release them.

Figure 4. Delay in Some of Packets.

In Fig. 5, we have gained an average delay of all packets that are sent over the network. The results show that in IMMSpeed algorithm approximately 50 percent of the packets will incur additional delay about 200 milliseconds in comparison with MMSpeed. However, these delays in the most cases, will not lead to the release packets and packets reach their destination in the specified deadline.

Figure 5. Delay in Some of Packets.

• V.    C onclusions

In this paper, we provide an optimized algorithm 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 reduces in the number of release packets that are sent to the destination.

Acknowledgment

Done in Abadan Branch, Islamic Azad University, Abadan, Iran.