Energy Conscious based Multipath Routing Algorithm in WSN

Published Online January 2016 in MECS

A wireless sensor network is a group of interconnected sensory nodes with organized computation, restricted power supply and transmission capability. Due to its restricted transmission and computational capability, the use of single path routing protocol is very incompetent. Further energy concerns, decrease the reliability of the network, which affects the Quality of Service. An important issue in wireless sensor networks is to design appropriate routing algorithms. Based on single-path routing various routing algorithms have been proposed. Wireless sensor networks protocol stack [1,2] is proposed to enhance the performance demands. Here the source selects single route for transmitting data towards the sink which propitiate the performance demands of the application. The path between the source and sink can be established with minimum reckoning complexity and system performance, but the restricted capacity diminishes the accessible throughput [3]. Single path routing is not amenable to link failures, there by humiliating the network performance. It will cause an extra burden and increased delay in data distribution if the dominant route fails to continue the data transmission. Therefore the single path routing is considered as a non effectual system to meet the performance demands of various applications like area monitoring, health care monitoring, environmental sensing and industrial monitoring.

Multi-path routing strategy came into reality to overcome the performance issues and to deal with the limitations of the single path routing strategy. Multiple routes are initiated between the source and the sink for data transfer [4]. The usage of these links entirely depends up on its routing strategies. Some routing algorithms use the best route, holding the alternate routes as a reserve and use it if the dominant route falls through . Some use all their routes synchronously to send data.

Multi-path routing approach provides route flexibility and reliable data transfer. Multipath routing [5] protocol is used to increase the reliability and QoS and makes the network energy efficient. In the fault tolerance zone, while forwarding the data, if a link or a node failure occurs, an alternate route is set for data forwarding without any interruption. Two methods can increases the data transmission reliability. In the first method multiple copies of the same data are assigned through multiple routes and in the second method the source appends a header data to the original data and forwards the incepted data packet over various routes.

Due to the resource constraints of WSN, enormous traffic consignments in the high data rate applications are prone to cramming, which highly influence the performance of the network [6,7]. To overcome this problem, data dissemination algorithms are used to increase the network competency by using more network resources. Multi-path routing renders the best resolution by splitting up the network traffic over various reachable routes and then compressing the probability of cramming. By sending the time critical data through shortest route and non time critical data through longest routes we can elevate the network throughput, end to end latency, and data delivery rate.

Some of the energy efficient multipath routing algorithms are Energy Efficient Multipath Routing [8], Energy Efficient Collision Aware Multipath Routing [9], Maximally Radio Disjoint Multipath Routing [10], and Low Interference Energy Efficient Multipath Routing Protocol [11].All are based on collision aware with minimal intrusion or load balancing. In this paper we consider these two condition namely collision avoidance and load balancing. In addition to this we propose a Multipath Energy Conscious Routing Algorithm (MECRA) which uses non-flooding method to initiate multiple routes between source and sink. The ability of the proposed system is to erect high quality, reliable paths.

The main criterion utilized by all the existing protocols is route disjointness. The route disjointness is labeled as node disjoint, link disjoint and partial disjoint. Node disjoint means there are no common nodes on the discovered routes. Link disjoint routes have multiple nodes in common, while there won’t be shared link between routes. Partial disjoint include routes that share multiple nodes between routes.

The essential criteria considered for discovering a set of routes is the route disjointness. Time varying properties of radio communication and resource restraint leads to a creation of some low quality routes. To overcome this problem several routing algorithms use several routing costs to make the best routing decision The basic components of routing cost function are route length, packet loss rate, delay, residual battery level. Once the routes are selected the function of the routing protocol is to allocate the network to improve performance demands such as throughput, data delivery ratio, delay and life time.

Network performance is influenced by low-power links routes and resource constraints, which leads to cramming. To overcome this problem, route reconstruction is made to reduce performance confusion. The three different situations to be considered to study the route discovery are,

• 1.    Failure of active route.

• 2.    Failure of all active routes.

• 3.    Failure of certain number of routes.

The rest of the paper is organized as follows: The related works are discussed in Section 2. Problem Statement is discussed in Section 3. Proposed Algorithm Multipath Energy Conscious Routing Algorithm (MECRA) is briefly illustrated in Section. 4. Simulation and Performance analysis are presented in Section. 5. Results and discussions are presented in section 6. Section 7 concludes the paper along with References.

• II.    Related Work

Query based multi-path routing protocol is used in Directed Diffusion Protocol [12], in which the sink initializes the routing process. The sink loads the concerned data through the network path which contains information concerning the task which will be performed by the sensors. During the data overload all the intermediate nodes store the concerned data obtained from their neighbours. The receiver node creates an incline [13] towards the nodes from which the data has been received. Multiple routes can be identified between each source and sink. In the next step, when the source discovers an event matched with the casual data in the concerned table, it forwards the data through all the constructed routes. The sink node selects a route based on the performance of the packet reception over each route. The selected route is used to transmit the data between the source and sink node. In order to maintain the discovered routes the sink node constantly sends low-rate concerned data over the surviving routes. The data can be transmitted through the other surviving route if there is a fault in dominant route providing fault tolerant routing.

In Braided Multipath Routing Protocol [14] similar to Directed Diffusion, several partially disjoint routes are constructed to provide fault tolerant routing. Using two route reinforcement messages, partially disjoint routes are constructed in this protocol. They are dominant route reinforcement message and alternative route reinforcement message. The route construction is initialized by the sink by sending a dominant route reinforcement message towards its best next-hop neighbour towards the sink and this process continues until the dominant reinforcement message reaches the source node. An intermediate node that is not a member of the dominant route will select the best next-hop neighbour towards the sink, and this process continues until the message reaches a node along with the dominant route which results in the formation of backup routes from all the intermediate nodes which are in the dominant route. Whenever a dominant route fails all the data can be transferred through to the alternate route.

An appropriated, scalable and localized multi-path search protocol [15] is used to identify multiple node-disjoint routes between the source nodes and sink node. It uses the load balancing algorithm to allocate the traffic over the multiple routes identified. By allocating the traffic over multiple node-disjoint routes, network life time is increased. In the network when an event triggers, the sensor nodes swap the data among themselves and one of these sensors is nominated as the source which initiates a route discovery process. The source node forwards the multiple Route-Request data to its neighbouring nodes.

The route establishment process is complete by setting a timer in the source node. Low quality paths are the one which are identified after the expiry of timer. After that the sink node rejects the route-request messages received from these routes. However no steps are taken with reference to the interference level gone through by the intermediate nodes and its effect on the performance of the network. On the other hand, this protocol creates multiple node disjoint routes and employs all the discovered routes.

To achieve energy efficient and low-latency communication in wireless sensor networks AOMDV (Inspired Multi-path Routing Protocol) [16] is designed by using cross layer information. The technique introduced in this protocol for route construction is similar to the technique introduced in AOMDV with few amendments. AOMDV-Inspired Multipath Routing Protocol uses hop-count optimal paths towards the sink node whereas AOMDV recognizes all link-disjoint routes between each pair of source and sink nodes. Here the sink node confirms a new route only if the first node is different from the previously discovered routes provided if the hop count is similar to the previous one. If the sink node receives a route-request with lower hop count then all the previously discovered routes is replaced with the newly discovered route.

In Energy Efficient and Collision Aware Multipath Routing Protocol [17], location information of the nodes is used to create two collision free routes on both sides of the direct line between the source-node and sink node. Interference is limited by keeping the distance between the two routes more than that of the interference range of the sensor nodes. During this stage the source node discovers two distinct set of nodes on both sides of the direct line between the source node and sink node. After discovering the neighbouring set, the source node broadcasts a Route-request packet towards these nodes to discover two node disjoint routes. To select their next hop the intermediate nodes follows the same technique used by the source node. Based on their distance to the sink and residual battery level the intermediate nodes set a back-off timer before broadcasting the received route request message. After receiving the route request message the intermediate node will set a back-off timer to restrict the route discovery flooding.

The neighbouring nodes with high battery level and shorter distance to the sink will set shorter back-off time. Due to this only a single node, at each stage will broadcast the received route-request packet towards the sink node. The sink node sends a route response in the reverse route towards the source on receiving the route request. The source initiates the data transmission through the established route when it receives the route reply. Data transmitted over minimum hop routes will reduce the delay and resource utilization but leads to packet loss and overhead of packet re-transmission.

To improve the packet delivery ratio, latency, and lifetime a method called Low Interference Energy Efficient Multipath Routing (LIEMRO) [18, 19] were designed. It includes a load balancing algorithm which distributes the source node traffic over multiple routes. In this method all nodes know about their neighbouring nodes and send only a limited number of control packets to the neighbours and looks after the successfully received packets from the neighbours. The sink node confirms the discovered route by sending route-reply through the reverse route when it receives the first route request packet. Whenever the source node overhears the message it receives a route-reply message which in turn forwards the information through the established route, and starts the construction of a new route by sending a new route-request packet towards the sink node. After constructing a new route the previous route is disabled. This is an iterative process and source node continues to build new routes as long as the new route provides higher end to end throughput, the sink node asks the source to disable the last constructed route. After attaining the Route Reply from the new route the source node splits the network traffic and transmits some portion of the traffic through this route using a quality based load distribution algorithm. Buffer capacity is not considered by LIEMRO.

The recent cutting edge design technology, considers the high bandwidth backbone network, Interference-Minimized Multipath Routing Protocol (IMMR) [20] steered to reinforce high data rate streaming in wireless sensor networks. Based on the availability of a specific hardware component, IMMR assumes a special network structure which tries to establish zone disjoint routes and allocates the traffic over the indentified routes. It assumes all the organized gateway nodes as final destinations. It is directly connected to the centre by using non-interrupting and high capacity links.

Route discovery process involves three important steps.

• 1.    Every source node elites one gateway node as its primary gateway node and establishes the shortest path towards the gateway node.

• 2.    All the one-hop and two-hop neighbours of the intermediate nodes are marked as the interference zone of the primary path along with the first route.

• 3.    The secondary and backup gateways nodes selected from  the  preferred sections are

determined by the primary gateway.

Depending upon the location of source node the preferred section is selected. In addition preferred gateway nodes should be located beyond the interference range of the primary gateway. The nodes that are not listed in the interference range of the primary path are considered as secondary and backup nodes. After the path construction process, both the primary and secondary routes are used with highest feasible data rate. A third route is maintained for route recovery during failure of nodes. If an intermediate node detects congestion then it intimates the source to reduce the data rate. Based on the time-varying properties of low power wireless links, data transmission over long hops results in higher packet loss rate.

• III.    Problem Statement

• IV.    Multipath Energy Conscious Routing Algorithm in WSN

Here we propose a Multipath Energy Conscious Routing Algorithm in WSN. Our proposed scheme consists of Neighbourhood Discovery, Multipath Construction and Data Transmission. This algorithm is based on the multipath scheme where multiple routes exist between each source node and the sink node. In this section we discuss about system model and assumptions for the proposed protocol and working principle of the proposed protocol.

• A.    Network Model and System Assumption

The network consists of ‘n’ number of sensor nodes which includes a sink node. The nodes are considered as stationary after the deployment. Consider a static sink node in the middle of the network having unlimited computation, memory, and battery power. The sink node is provided with information like ID and location of the source nodes in the network. Every node knows their position in the network. All sensor nodes are equivalent and massively organized. Communication range of every node is equivalent and predefined.

• B.    Multipath Energy Conscious Routing Algorithm

In order to avoid flooding and take the benefit of both load balancing and collision aware mechanism for energy conservation, we propose a multipath energy conscious routing algorithm. When the sink node needs the data from a particular source node this algorithm creates a routing path between the source and the sink node. The proposed protocol consists of three stages namely Neighbourhood Discovery, Multipath Construction, and Data Transmission.

• C.    Neighbourhood Discovery

In this phase every node transmits a control packet containing its node ID, residual energy, and its location to all the other nodes. It waits for the control packets from them. After receiving the control packets, each node discovers its neighbouring nodes. Now every node has the partial view of the network which is as demonstrated in the Fig 1.

Fig.1. Neighbourhood Discovery

• D.    Multipath Construction

Multipath Construction phase starts after the discovery of Neighbouring node in which every node holds their neighbour information. Assume that the sink node knows the location of the source node and based on its location, the sink node proceeds the route request process. The main concept is that, there are two types of nodes namely dominant node and alternate node. The proposed algorithm determines two routes from the sink node to the source node called as dominant route and alternate route respectively. The dominant route is constructed with the best feasible neighbour with the minimum Location Factor (LF) and the alternate route is constructed with the next best feasible neighbour with the next minimum Location Factor (LF). Location factor describes the minimal distance between the source and neighbour node.

Fig.2. Multipath Construction

If the sink node itself is a dominant node then it selects two neighboring nodes in which the node with the minimum location factor becomes the next dominant node and the node with the next minimum location factor becomes the alternate node. In Fig 2 node (a), which is connected by a bold line has the minimum location factor, denoting the dominant node and is in the dominant route from the sink to the source. Node (b), which is connected by dashed lines has the next minimum location factor denotes an alternate node and is in the alternate route from the sink to the source. All other intermediate nodes follow the same procedure to find its corresponding neighbouring node until it reaches the source node. As the route request reaches the source node one dominant route and multiple alternate routes are constructed between the sink node and the source node.

In order to find the dominant route both the dominant and alternate nodes are called for finding a dominant node towards the source. If it is a dominant node it will broadcast its node type to the dominant routes among its neighbours and scan for the nodes with minimum location factor towards the source node. Comparably if it is an alternate node it will broadcasts its node type to the alternate routes among its neighbours and scan for the node with next minimum location factor towards the source. It is found that the neighbouring nodes can have two feasible nodes called dominant node and alternate node. If the node of origin is dominant, then the node type of the found neighbour will be swapped to dominant node. If the node of origin is an alternate, then node type of the found neighbour will not swapped if it has already been assigned a node type. In case it has not been assigned any node type, it will be assigned as alternate node.

Then every node except the dominant is put into sleep mode. To avoid collision only one route is made active between the source and the sink nodes to reduce interference from the other routes. These factors help to save energy. If there is a deadlock in the dominant route the protocol selects alternate route with the best metric to transfer data. If all routes are disturbed and no route is available between the source and sink then the process starts from the Neighbourhood Discovery phase.

Input: Set of n sensor nodes randomly distributed.

Output: One dominant and multiple alternate routes from source to sink.

repeat if (node == sinknode) then

Find Dominant Route () ;

Find Alternate Route () ;

else if ( node == Dominant) then

Find Dominant Route () ;

Find Alternate Route () ;

else if ( node == Alternate ) then

Find Dominant Route () ;

end if until (node _= Source)

procedure Find Dominant Route()

if ( node == Dominant) then

Broadcast DOMINANT ;

Search for the best node;

node _ Dominant;

end if if (node == Alternate) then

Broadcast ALTERNATE;

Search for the best node and prefer Dominant;

if (node _= Dominant) then node _ Alternate;

end if end if end procedure procedure Find Alternate Route()

if node == Dominant then

Search for the next best route node accept Dominant;

if (( node _= Dominant ) && (node _= Alternate )) then node _ Alternate ;

end if end if if (node == Alternate) then

Exit () ;

end if end procedure

• E.    Data Transmission

Data transmission takes place between source node and sink after the multipath construction phase. Although both the dominant and alternate routes are available, data is transmitted over the dominant route only. The source node utilizes the alternate route, only if the dominant route is broken. The remaining nodes which are not in the active route will go to sleep mode in order to save energy. If all the routes are disturbed and no route is available between the source and sink node then the process starts from the route discovery process.

• F.    Energy Model

Energy modeling in WSN is based on the theoretical energy consumption of the existing platforms. In the energy modeling concept we have considered three modes of energy consumption. The energy consumed due to transmission and reception of packets, energy consumed by nodes while in sleep mode and finally the energy consumed by the nodes in active mode.

• V.    Simulation

• A. Implementation

The simulation of WSN is carried out using NS 2.3.4. Sensor nodes are deployed in a random fashion to create homogeneous and heterogeneous WSN’s. As the nodes deployed in the network are communicating wirelessly based on their distance, transmission range etc., a wireless channel is used. Simulation studies show that MECRA performs better, considering the parameters like throughput, packet delivery ratio and average Energy Consumption.

This section discusses and presents the simulation results for the performance study of MECRA protocol and compares it with LIMERO and AOMDV protocol.

Simulation parameters are presented in Table 1 and the results obtained are shown below.

Table 1. Simulation parameters

Parameter	Value
Simulator	NS 2.3.4
Simulation Area	100*100
Number of Nodes	20,30,40
Initial battery capacity	18720 Joule
Data packet size	512 bytes
Simulation duration	600sec

Parameters like Packet Delivery Ratio, Throughput (sec) and Average Energy Consumption are monitored at various time intervals. The results are described in the next section.

• VI.    Reults And Discussions

As discussed earlier, energy conscious WSN deployment is a challenging task, due to large number of parameters. NS 2.3.4 platform is used for coding of MECRA and finally, the comparative performances of all the algorithms are explained.

• A.    Packet Delivery Ratio

The ratio of the number of data packets delivered to the destination is represented as a ratio of number of packets received to the number of packets sent. The greater the value of PDR means better performance of the protocol. The result is shown in Fig 3. The proposed scheme Multipath Energy Conscious Routing Algorithm is compared with AOMDV-Inspired Multipath Routing Protocol and Low-Interference Energy Efficient Multipath Routing Protocol and our algorithm outperforms the compared algorithms in terms of high packet delivery ratio. The packet delivery ratio shows continual improvement with the increase in the number of nodes.

Packet Delivery Ratio = ∑ Number of packet receive / ∑ Number of packet send

• B.    End-to-End Delay

Throughput is the average time taken by a data packet to arrive at its destination. It also includes the delays caused by route discovery process and the queue in data packet transmission. The proposed scheme Multipath Energy Conscious Routing Algorithm is compared with AOMDV-Inspired Multipath Routing Protocol and Low-Interference Energy Efficient Multipath Routing Protocol. Our algorithm shows a minimal throughput when compared with other algorithms. It is observed that the throughput decreases with the increase in the number of nodes. The result is shown in Fig 4.

End to End Delay =∑ (arrive time – send time) / ∑ Number of connections

Fig.4. End-to-End Delay

• C.    Average Energy Consumption

It is the average of amount of energy consumed due to transmission and reception of data packets. The proposed scheme Multipath Energy Conscious Routing Algorithm is compared with AOMDV-Inspired Multipath Routing Protocol and Low-Interference Energy Efficient Multipath Routing Protocol. Comparing with other algorithms, maximum Energy Consumption is considerably low in our proposed method. The result is shown in Fig 5.

Packets lost = Number of packets sent – Number of packets received.

Fig.3. Packet Delivery Ratio

Fig.5. Average Energy Consumption

• VII.    Conclusions

In this paper, we have proposed a Multipath Energy Conscious Routing Algorithm (MECRA) in WSN. The proposed protocol is designed to decrease the routing overhead, improve the latency and packet delivery ratio by discovering multiple routes from the source to the sink. The detailed analysis shows how the proposed protocol overcomes the drawback of the existing protocols. The proposed protocol creates the routes (Dominant and Alternate) between source node and sink node without using flooding mechanism and also affords collision awareness and load balancing methods which makes it energy conscious and helps to enhance the network performance and lifetime. The simulation result explains the latency, packet delivery ratio and total energy consumed. Based on our simulation results we have proved that our proposed Multipath Energy Conscious Routing Algorithm (MECRA) reduces the routing overhead and attains more throughputs with reduced packet loss and delay, when compared with the existing protocols.