An ImprovedWireless Sensor Network Routing Algorithm

Shengmei Luo，Xue Li，Yiai Jin，and Zhixin Sun

（1.ZTE Corporation，Shenzhen 518057，China；2.School of Internet of Things，Nanjing University of Posts and Telecommunications，Nanjing 210003，China）

An ImprovedWireless Sensor Network Routing Algorithm

Shengmei Luo1，Xue Li2，Yiai Jin1，and Zhixin Sun2

（1.ZTE Corporation，Shenzhen 518057，China；2.School of Internet of Things，Nanjing University of Posts and Telecommunications，Nanjing 210003，China）

High performance with low power consumption is an essential factor in wireless sensor networks（WSN）.In order to address the issue on the lifetime and the consumption of nodes in WSNs，an improved ad hoc on-demand distance vector routing（IAODV）algorithm is proposed based on AODV and LAR protocols.This algorithm is a modified on-demand routing algorithm that limits data forwarding in the searching domain，and then chooses the route on basis of hop count and power consumption.The simulation results show that the algorithm can effectively reduce power consumption as well as prolong the network lifetime.

wireless sensor network；low power consumption；lifetime；AODV；LAR

1 Introduction

Wireless sensor networks（WSN）consist of a large number of cheap micro sensor nodes that are deployed in the examination area，aiming at forming a multi-hop self-organization network system by wireless communication［1］.Applied to WSN，the ad hoc on-demand distance vector routing（AODV）［2］protocol is a typical on-demand routing protocol.It is a combination of dynamic source routing（DSR）［3］and destination se-quenced distance vector（DSDV）［4］.AODV borrows the basic programs of route discovery and route maintenance from DSR，and Hop-by-Hop route，destination node serial number and periodic update mechanism in routing maintenance phases from DSDV.

One major disadvantage of WSN is the energy limitation of its nodes.However，AODV does not consider a node's current residual energy when it establishes routing.Much research has been done to improve the AODV protocol by solving the problem of energy consumption in WSN.The existing research work has just paid attention to controlling the number of packets in the process of establishing routing，or focused on the energy consumption of nodes and the path load.In fact，the improvement is not ideal.In this paper，we propose an improved ad hoc on-demand distance vector routing（IAODV）algorithm based on the existing location-aided routing（LAR）routing protocol to reduce the number of route request（RREQ）packets. The IAODV algorithm uses the improved routing control packets and streamlined routing tables and route request tables.It simplifies the route discovery process and reduces the number of routing control packets and the power consumption of the network.This algorithm also uses the path selection function that takes the hop and energy consumption into account.This function helps optimize the power consumption of sensor network nodes and prolong the lifetime of the network.

2 Related Work

Location-based routing protocols，such as geographical adaptive fidelity（GAF）and geographical and energy aware routing（GEAR）［5］，［6］，need to wake up the sensor nodes nearest to the tracking target in an application that wants to obtain information related to the target position.The Greedy Perimeter Stateless Routing（GPSR）［7］protocol is a typical locationbased routing protocol.Its main strategy is to choose the node that is closest to the sink nodes as the next hop in every jump. Network nodes then use the classical flooding routing protocol［8］to forward packets in the form of broadcast.This protocol is based on flooding，so the signaling overhead is huge.

Combining the location-based routing protocol and flooding routing protocol，the LAR routing protocol is proposed in［9］. LAR uses the location information to restrict the flooding range of query packets.Based on the concept of expectation domain，location information is used to restrict the flooding range of RREQ，reduce the number of broadcast packets，reduce the power consumption of the network，and improve the network performance［9］，［10］.These proposed routing protocols use a series of mechanism to reduce the number of packets transferring in the network in order to make routing overhead relatively small.However，they do not take the network nodes' limited energy into account，so network nodes cannot efficiently send packets in the limited lifetime of the network.

An enhancement to the AODV routing protocol is proposedin［11］.It uses cluster-based mechanism to support congestion control in a mobile ad hoc network（MANET）.The main feature of this approach is clustering and the selection of the cluster head is on the basis of the congestion status of the nodes. This protocol is highly efficient in dealing congestion by achieving QoS constraints（good packet delivery ratio，low delay and reduction of packet drops），as well as energy efficient. However，it reselects the cluster head frequently due to the rapid energy consumption of the cluster head.

Energy values of the nodes and forwarding packets along the path of least energy consumption are evaluated in［12］，making the network adaptive in nature.However，the influence of the hop count on energy consumption of the whole network is not fully considered in［12］.The distributed Dynamic Route Change Algorithm（DRCA）［13］dynamically finds a shorter route to the destination by using the hello message of neighbor in the AODV routing protocol.DRCA first changes the hello message format of AODV to make it contain the list of recently forwarded destination，hop count and sequence number.The nodes that receive this hello message decide whether they change the next hop to the destination or not by comparing the hop count and sequence number in their routing table to those in the received hello message.However，the impacts of power consumption of broadcast packets are ignored in［13］.A new maximum-energy Local Route Repair（LRR）approach with multicast AODV routing protocol is proposed in［14］.This repair mechanism provides each node in the network with route establishment capability.However，the impacts of power consumption of broadcast packets and transmission hops are also ignored in［14］.

Based on the AODV protocol's routing selection criteria，the load path and the quality of the link are considered in［15］in order to save energy and prolong the network lifetime.Three factors of noise ratio，the number of active neighbor nodes and each node's queue state of filling are considered to improve the AODV protocol，and improve the performance of the network［15］.However，this method［15］may waste sources if it uses certain a path frequently and makes energy consume quickly while there is much left energy in other routes of the network.Piggyback and Weighted neighbor stability Ad hoc On -demand Distance Vector routing（PWAODV）［16］reduces the route cost and network delay effectively by using piggyback mechanism and weighted neighbor stability algorithm，However，the count of packets does not get good control in this method，which makes power consumption unsatisfactory.AODV++ protocol［17］establishes routes from the source node to the destination node according to the node's residual energy and traffic load，but it does not fully consider the influence of the hop count on the whole network's energy consumption.

In order to solving the problems of AODV and improved AODV protocols，we propose an improved routing algorithm—IAODV in this paper.The algorithm limits forwarding packets in a certain area，and uses the path selection function that considers the hop and energy consumption.It realizes the decrease of the packets number while reducing power consumption and prolonging the lifetime of wireless sensor network.

3 IAODV Algorithm

3.1 Format of Packets

3.1.1 Route Request（RREQ）Packets

On the basis of the original format of RREQ packets，the proposed RREQ packets（Fig.1）remove five flags，transform the original reserved field to the distance field to record the distance from the current node to the destination node，and set up the energy field to record total nodes' residual energy in each routing path.At the same time，RREQ takes out the destination sequence number and originator sequence number field.

3.1.2 Route Reply（RREP）Packets

The format of RREP packets（Fig.2）is basically consistent with RREQ packets.In RREP packets，the type field is set to 10，and RREP packets change the distance field of RREQ tothe reserved field and set it to 0.The RREP ignores the reserved field when the node accepts RREP packets.

▲Figure 1.Route request packet format of IAODV.

▲Figure 2.Route reply format of IAODV.

3.1.3 Route Error（RERR）Packets

RREQ removes the destination sequence number and originator sequence number field and switches to the path selection function for path selection.Therefore，as shown in Fig.3，the proposed RERR packets，based on the original RERR packet format，take out the destination count and unreachable destination sequence number field.At the same time，RERR sets up the failing packet ID field to record the first packet sequence number that fails to send messages.

3.1.4 Routing Table and Routing Request Table

The IAODV routing table（Fig.4）removes the source node serial number field，destination node serial number mark field，another state or routing marks field，the hop count from the source node to destination node field，and the forward pointer table field from AODV routing table.The IAODV algorithm uses the streamlined routing table and route request table，and simplifies the route discovery process.

Each node that receives RREQ puts the source node address and RREQ ID information into the routing request table（Fig.4）.The node automatically deletes entries in the routing request table if going beyond the time limit.

3.2 Routing Algorithm

The algorithm uses the distance strategy of the LAR control routing lookup strategy to determine the size of the search area.Looking for routing area is then limited to a small search domain，which reduces routing requests.The routing algorithm assumes that each node knows its own energy consumption in the network and that each node is fixed.In the initialization phase of the network，nodes in the network use GPS to determine their locations，and then send their own coordinates to the nodes within the scope of one hop.The form of flooding is kept until each node owns the entire topological graph of network.

▲Figure 3.Route Error packet format of IAODV.

▲Figure 4.IAODV routing table and routing request table.

When a link is disconnected，the node uses unicast to the source node for noticing the link failure.The RERR packets point out the unreachable destination nodes.

▲Figure 5.Routing of RREQ packets.

▲Figure 6.Routing of RREP packets.

▲Figure 7.Flooding.

▲Figure 8.Inhibition flooding.

In Figs.7 and 8，A is the source node and D is the destination node.Only the black nodes forward RREQ during the routing process.When Fig.7 is compared with Fig.8，it is seen that the inhibition flooding method can effectively reduce the number of RREQ packets.This is duo to in the process of inhibition flooding，routing area is limited to a small search domain，which reduces routing requests.

3.2.1 Path Selection

The power consumption of wireless sensors mainly includes consumption in perception，processing，communication，and positioning.Among them，the consumption of communication is the biggest of all.Each source node sends data to destination node consuming energy that is connected with the hop count.A path selection function is defined by the node's residual energy and hop count in the process of routing selection.A routing in which the nodes'average residual energy is biggest is selected as the best routing.In this way，the node's energy consumption is optimized and the network's lifetime is prolonged.

The IAODV related definitions are as follows.

Definition 1:a route is expressed asri=a1，a2，...，aj，where a1is the source node，ajis the destination node，andNis the number of hops from the source node to destination node.

Definition 2:Eiis the residual energy ofai，the average residual energy of each node on the routeri:

Definition 3（path selection function）:

whereRis the set of all paths from the source node to the destination node.

但小編最喜歡的是武俠題材的游戲。它不但包含有文字和畫面兩個元素，還有一種身臨其境的代入感和掌控感，可以自由地替主角做出選擇，左右劇中人物的命運。

Equations（1）and（2）show that the path that has more residual energy and less hops is more likely to be selected.When paths have the same residual energy，the path with the least hops is selected.When paths have the same hop count，the path with the most residual energy is selected.

4 Simulation Experiment

4.1 Simulation Environment

In order to verify the IAODV algorithm performance，we implemented a simulation experiment on the NS-2.35 simulation platform.The simulation parameters were set as shown in Table 1.

The simulation experiment evaluates the following indicators:

（1）The number of survival nodes，which reflects the lifetime of the network in different periods

（2）The rate of residual network energy，which is the proportion of the sum of all nodes'residual energy and the initial total energy and reflects the power consumption of the routing algorithm

4.2 Simulation Results and Analysis

In the experiment，IAODV is compared with AODV，PWAODV［16］and AODV++［17］in the same simulation environment.

According to the simulation results shown in Fig.9，the polylines of the four algorithms coincide at 0-30 s.As the simulation time goes on，the number of survival nodes in the net-work tends to reduce no matter which protocol is adopted. With IAODV，the first node death time is at 50 s and there are five dead nodes at the end of the simulation.With AODV++，the first node death time is at 46 s and there are eight dead nodes at the end of the simulation.With PWAODV，the first node death time is at 44 s and there are 10 dead nodes at the end of the simulation.With AODV，the first node death time is at 40 s and there are 13 dead nodes at the end of the simulation.

▼Table 1.IAODV simulation parameter values

▲Figure 9.Living nodes.

The death time of nodes in the AODV-based network is the earliest and the number of dead nodes at the end of the simulation is also the most in this network，because the AODV protocol does not consider the energy consumption of nodes in the process of routing discovery.PWAODV uses piggyback mechanism and weighted neighbor stability algorithm to reduce the route cost and network delay effectively.The AODV++protocol establishes routes from the source node to destination node according to the residual energy and traffic load of nodes.Compared with AODV，PWAODV and AODV++have certain improvement in the energy consumption of the network.However，they fail to consider the influence of the hop count to the energy consumption of the whole network.

IAODV considers the hop count and energy consumption by using the path selection function.Compared to the other three protocols，it achieves the latest death time of nodes and the fewest dead nodes.In this way，the IAODV algorithm reduces the number of dead nodes in limited time and prolongs the lifetime of the network.

Fig.10 shows that the ratio of residual network energy tends to reduce no matter which protocol is adopted.In an IAODV based network，the nodes first confirm their own locations by GPS and send the coordinate to all the nodes in one hop. Therefore，the ratio of residual energy is low at the initial stage of the simulation.According to Fig.10，the residual energy ratio of the IAODV based network is higher than those of the networking using the other three protocols，and the gap becomes bigger as the simulation time goes on.

▲Figure 10.The ratio of residual energy.

According to Fig.11，the routing costs of the four protocols are small，when the number of nodes is small.However，with the increase of nodes，the routing cost of AODV dramatically increases.The increase of the routing costs of AODV++and PWAODV is smaller than AODV.IAODV has the least increase of the routing cost because it optimizes the network routing process.

5 Conclusions

We propose IAODV，an improved routing algorithm，for realizing low power consumption and longer lifetime of WSN.The proposed algorithm combines the AODV and LAR routing protocols and gives full consideration to the network's energy consumption problem.According to the simulation results，this al-gorithm achieves the goal of improving the performance of the network and prolonging the lifetime of network.

▲Figure 11.Routing cost.

［1］L.Sun，J.Li，and Y.Cheng，Wireless Sensor Networks，Beijing，China:Tsinghua University Press，2005.

［2］Ad Hoc On-Demand Distance Vector（AODV）Routing，IETF RFC3561，Jul.2003.

［3］The Dynamic Source Routing Protocol（DSR）For Mobile Ad Hoc Networks For IPv4，IETF RFC 4728，F(xiàn)eb.2007.

［4］C.E.Perkins and P.Bhagwat，“Highly dynamic destination-sequenced distancevector routing（DSDV）for mobile computers，”Computer Communication Review，vol.24，no 4，pp.234-244，1994.doi:10.1145/190314.190336.

［5］W.B.Heinzelman，A.P.Chandrakasan，and H.Balakrishnan，“An application-specific protocol architecture for wireless microsensor networks，”IEEE Transactions on Wireless Communications，vol.1，no.4，pp.660-670，Oct.2002.doi: 10.1109/TWC.2002.804190.

［6］K.Akkaya，F(xiàn).Senel，and B.McLaughlan，“Clustering of wireless sensor and actor networks based on sensor distribution and connectivity，”Journal of Parallel and Distributed Computing，vol.69，no.6，pp.573-587，Jun.2009.doi:10.1016/ j.jpdc.2009.02.004.

［7］B.Karp and H.T.Kung，“GPSR:Greedy perimeter stateless routing for wireless networks，”in 6th Annual International Conference on Mobile Computing and Networking，Boston，USA，2000，pp.243-254.

［8］C.-Y.Chong and S.P.Kumar，“Sensor networks:evolution，opportunities，and challenges，”Proceedings of the IEEE，vol.91，no.8，pp.1247-1256，Aug.2003. doi:10.1109/JPROC.2003.814918.

［9］Y.-B.Ko and N.H.Vaidya，“Location-aided routing（LAR）in mobile ad hoc networks，”Wireless Networks，vol.6，no.4，pp.307-321，Jul.2000.doi:10.1023/A: 1019106118419.

［10］H.Asenov and V.Hnatyshin，“GPS-enhanced AODV routing，”in International Conference on Wireless Networks，Las Vegas，USA，Jul.2009，pp.1-7.

［11］N.Phate，M.Saxena，and M.A.Rizvi，“Minimizing congestion and improved QoS of AODV using clustering in mobile ad hoc network，”in Recent Advances and Innovations in Engineering，Jaipur，India，May 2014，pp.1-5.doi:10.1109/ ICRAIE.2014.6909217.

［12］A.P.Patil，B.Varsha Chandan，S.Aparna，et al.，“An improved energy efficient AODV routing protocol for MANETs，”in Eleventh International Conference on Wireless and Optical Communications Networks，Vijayawada，India，Sept.2014，pp.1-5.doi:10.1109/WOCN.2014.6923063.

［13］Y.Choi，D.Kang，and S.Bahk，“Improvement of AODV routing protocol through dynamic route change using hello message，”in International Conference on Information and Communication Technology Convergence，Busan，South Korea，Oct.2014，pp.117-121.doi:10.1109/ICTC.2014.6983096.

［14］P.Jain and A.Suryavanshi，“Energy efficient local route repair multicast AODV routing schemes in wireless ad hoc network，”in International Conference on Advanced Communication Control and Computing Technologies，Ramanathapuram，India，May 2014，pp.1168-1173.doi:10.1109/ICACCCT. 2014.7019282.

［15］A.Singh，A.Konsgen，and C.Goerg，“Enhancing AODV performance by improved link metrics，”in 5th International Conference on Information and Automation for Sustainability，Dec.2010，pp.183-188.doi:10.1109/ICIAFS. 2010.5705657.

［16］N.Wang and Y.Cao，“An improved AODV protocol with lower router cost and smaller delay-PWAODV，”in Fourth International Conference on Intelligent Computation Technology and Automation，Shenzhen，China，Mar.2011，pp. 435-438.doi:10.1109/ICICTA.2011.393.

［17］S.Ren，H.Han，B.Li，et al.，“An improved wireless sensor networks routing protocol based on AODV，”in 12th IEEE International Conference on Computer and Information Technology，Chengdu，China，Oct.2012，pp.742-746.doi: 10.1109/CIT.2012.153.

Manuscript received:2015-04-02

Biographies

Shengmei Luo（luo.shengmei@zte.com.cn）received his master degree in communication and electronics from Harbin Instituted of Technology in 1996.He is the chief architect of the Cloud Computing and IT Institute of ZTE Corporation.His research interests include cloud computing，network storage，and big data.

Xue Li（lixue7168@163.com）is a graduate student in computer software and theory at Nanjing University of Posts and Telecommunications.Her research direction is software application technology based on computer networks.

Yiai Jin（jin.yiai@zte.com.cn）received his master degree in computer science from Jilin University in 2005.He is a senior engineer of ZTE Corporation.His research interests include cloud computing and security.

Zhixin Sun（sunzx@njupt.edu.cn）received his PhD degree in aeronautics and astronautics manufacturing engineering from the Nanjing University of Aeronautics and Astronautics in 1998.He is a doctoral supervisor at Nanjing University of Posts and Telecommunications.His research interests include computer application and network safety，multimedia communications，and Internet of Things.

This work is supported by the National Natural Science Foundation of China under Grant Nos.61373135，60973140，and 61170276，Key University Science Research Project of Jiangsu Province under Grant No. 12KJA520003，Project for Production Study&Research of Jiangsu Province under Grant No.BY2013011，and The Science and Technology Enterprises lnnovation Fund Project of Jiangsu Province under Grant No. BC2013027.