JIAO Guo-tai(焦国太), MENG Qing-feng(孟庆丰)

(1. State Key Laboratory of Robotics and System, Harbin Institute of Technology, Harbin 150001, China;2. College of Mechatronics Engineering, North University of China, Taiyuan 030051, China;3. Robotics Research Center,North University of China, Taiyuan 030051, China)

A new algorithm for wireless sensor network based on NS-2*

JIAO Guo-tai(焦国太)1,2, MENG Qing-feng(孟庆丰)1,3

(1. State Key Laboratory of Robotics and System, Harbin Institute of Technology, Harbin 150001, China;2. College of Mechatronics Engineering, North University of China, Taiyuan 030051, China;3. Robotics Research Center,North University of China, Taiyuan 030051, China)

Considering wireless sensor network characteristics, this paper uses network simulator, version 2 (NS-2) algorithm to improve Ad hoc on-demand distance vector (AODV) routing algorithm, so that it can be applied to wireless sensor networks. After studying AODV routing protocol, a new algorithm called Must is brought up. This paper introduces the background and algorithm theory of Must, and discusses the details about how to implement Must algorithm. At last, using network simulator (NS-2), the performance of Must is evaluated and compared with that of AODV. Simulation results show that the network using Must algorithm has perfect performance.

wireless sensor networks; routing protocol; network simulator, version 2 (NS-2); Must algorithm

0 Introduction

With the development of computer technology, network technology and wireless communication technology, by using a smaller, more inexpensive and low power embedded system and network technology, many new information acquisition and processing modes are developed. The wireless sensor network is one representative field among them[1].

Wireless sensor network consists of a large number of randomly distributed sensors, data processing units and small nodes of communication module. The various sensors placed among the nodes are used to measure the peripheral environment parameters, bring together data by way of the network, and transmit them in the network or through the upper network[2].

In wireless sensor network, there are a large number of sensor nodes. The differences of the application and monitoring physical signal decide the types of the sensors. Additionally, the function and performance of these nodes are not the same. The system requires a miniaturized and commonly used embedded operating system, for example, TinyOS, μCOS-II and embedded Linux[3].

In the traditional wireless sensor networks, nodes lie in the monitored area arbitrarily. Nodes form network by self-organization and transmit the monitored data to the groove nodes through multi-hop relay. Eventually the entire region data is transmitted to the remote center for centralized treatment with the help of distance or temporarily established slot link.

1 Protocol stack of wireless sensor network

So far, there is not a standard protocol stack about wireless sensor network[4].

Fig.1 Protocol stack of wireless sensor network

Fig.1 shows a kind of protocol stack of one wireless sensor network. It includes two aspects: communication and management. Communication contains physical layer, data link layer, network layer, transport layer and application layer, which is somewhat analogous to the seven-layer model of open system interconnect (OSI)[5]. Management includes power management, mobile management and collaborative management. The communication realizes the information transmission among the network nodes. Nodes deliver the received data to the management plane, and the management layer decides how to handle the data. Management layer is responsible for the detection and control of node so that the node can work properly.

2 AODV routing algorithm

Ad hoc on-demand distance vector (AODV)[6-7]routing protocol is a kind of reactive routing protocol. It has the functions of route discovery and route maintenance for dynamic source routing (DSR) protocol, and it uses hop-by-hop routing that destination-sequenced distance vector (DSDV) uses, sequence number and beacon message[8].

AODV routing protocol has three types of message control frames: route request (RREQ), routie resply (RREP) and route error (RERR). When source node sends data to destination node, firstly it searches out the target node in its own routing table. If the route exists and is effective, then it sends the data immediately; If the corresponding route does not exist or route exists but has been marked as invalid, the source node will open a flood route discovery process. Afterward the source node creates a RREQ and broadcasts it to its adjacent node. To avoid unnecessary large broadcast range, AODV adopts expanded search technology, setting a RREQ and time to live (TTL) value. If one RREQ has no response due to no corresponding answer RREP, AODV broadcasts a RREQ again and also increases TTL value and broadcasts signals. This process continues until the route has been found or TTL value has reached the allowable maximum value.

When the intermediate nodes receive a RREQ, they judge whether it is RREQ processed. If it is, then discard it simply; If it is a newly received RREQ, create or update it toward the target node along the reverse path, (which can be used when the target node sends RREP to the source node), and then search the routing table. If there is no an active route toward the target node, broadcast TTL value (now TTL value is subtracted 1), then No.0 RREQ floods the process continually; If an intermediate node confirms that there is an positive (effective) target routing toward itself and the sequence number of target node is greater than or equals to the RREQ sequence number, it will answer RREP to the source node simplex wave routing directly along the reverse path and inform the target nodes to ensure the route is bidirectional. After the target node receives a RREQ, it no longer broadcasts RREQ. It establishes the reverse path first and generates a RREP, including a new sequence number and other information. RREP is transmitted to the source node along the reverse path of simplex wave. When the intermediate node receives RREP, it will build up a route to the target node, and update the sequence number and other relevant information. After the source node receives RREP, it will establish route and begin to transmit data. In RERR there is a linked list. Because of a broken link this list can not reach all destination nodes.

3 Principle of Must algorithm

Must algorithm is mainly based on breadth-first tree algorithm. Especially, assuming that there are thirty nodes in a region, node number is from one to thirty. Firstly, select one node as the root node and it sends a RREQ message. Before the root node transmits a request information, two parameters are given to it, the first parameter indicates the child node point of the root node, and the second parameter indicates the maximum number of the tree. Once there are nodes receiving a RREQ message, they will send RREP information, a link with the root node is established, and the others will establish their own sub-tree similarly, thus a breadth-first tree is established. When a node is to send data, the direction that the packets to be sent must be indicated. When transmitting the data packets to the parent node, the node that receives data packets checks whether it has transmitted the data packets. If not, transmits the packets according to the same rules, otherwise it discards the packets.

In Must algorithm, recv and command functions are the most important. Both the two functions are inherited by the same class agent. Command function defines the various commands and can set the parameters of the route by the commands when simulating. The recv function is the processing function that the routing layer receives a data packet. In the network simulator (NS) mobile node architecture, routing layer receives only the data sent from the up level and only sends data to the lower level. Through these functions, the routing layer can receive the data from the up-level algorithm and process it. The functions are the key part of the algorithm.

4 NS-2 simulation steps

In the preparation of simulation script, set some necessary attributes of the models, such as channel type of the node, media access control (MAC)[9,10]layer protocol, queue type, the scene size and number of nodes.

The moving scene parameters and flow scene parameters in the simulation are shown in the following Tables 1 and 2, respectively.

Table 1 Moving scene parameters

Table 2 Flow scene parameters

4.1 Performance comparison between Must and AODV algorithms

According to the above results, Table 3 lists the difference of AODV and Must algorithms in performance.

Table 3 Performance comparison of AODV and Must algorithms

ParametersMustAODVPacketdeliveryrate0．9991．0Controlpacketspercentage(%)0．130．022Averagedelay(s)0．0170．020

4.2 Defects of Must algorithm

Must algorithm is simulated in the form of animation. Simulation time is set to 200 s. In the 200 s part nodes fail because the energy is too low. And the child nodes number is more, the number of the layers composed by the same number of nodes is less required and the energy consumption is less. As shown in Fig.2, a lot of nodes' energy is consumed and the energy of the node in the tree layer is consumed relatively early.

Fig.2 Diagram of node energy consumption

Fig.3 shows the consumption speed when changing the maximum node to limit the node energy. C0 means no limit, C3 means the child node for 3.10 s before the route setting up, where the energy consumption is relatively small and slow. Therefore, through the above analysis, it can be seen that the closer to the root node, the more quickly the node energy consumes. In addition, if the algorithm is more suitable for static network environment, it is better.

Fig.3 Diagram of node energy consumption speed

5 Conclusion

This paper puts forward a new Must amgorithm based on AODV routing protocol. The Must algorithm is designed by using breadth-first tree to enable all nodes in the region to self-organize network. The center node collects the information from other nodes to achieve information collection and monitoring. Must algorithm is simulated and analyzed by NS-2. The results show that Must algorithm increases the network efficiency and reduces the network load.

[1] CHEN Lin-xing. Wireless sensor network technology and application. Beijing: Publishing House of Electronics Industry, 2009.

[2] ZHENG Shao-ren, WANG Hai-tao. Ad hoc network technology. Beijing: the People's Posts and Telecommunications Publishing House, 2005.

[3] SUN Ting, YANG Yong-tian. The wireless sensor network technology. Electronic Technology Application, 2006, 6: 1- 6.

[4] WANG Zhao-qiang, GE Wan-cheng, PI Kun-bao. Using NS-2 for wireless network simulation. Modern Electronic Technique, 2004, 22: 27-29.

[5] LI Ya-dong, CUI Wen-qiang, LI Dan-lan, et al. Research based on OSI model. In: Proceedings of IEEE 3rd International Conference on Communication Software and Networks(ICCSN), Xi’an, China, 2011: 554-557.

[6] Hassnawi L A, Ahmad R B, Yahya A. Modify AODV routing protocol to improve motorway surveillance system performance. International Journal of Computer Science Issues, 2012, 9(2): 52-62.

[7] Ambore B, Suma R, Mungara J. Optimal and robust framework for enhancing network lifetime using power efficient AODV in mobile Ad-hoc network. In: Proceedings of the 3rd International Conference on Trends in Information, Telecommunication and Computing Lecture Notes in Electrical Engineering, 2013, 150: 337-343.

[8] CUI Li, JU Hai-ling, MIAO Yong, et al. Overview of wireless sensor networks. Journal of Computer Research and Development, 2005, 42(1): 163-174.

[9] YU Fan, Biswas S. Self-organizing MAC protocol switching for performance adaptation in wireless sensor networks. Advances in Computing and Communications, 2011, 192: 54-67.

[10] Nguyen K, Meis U, JI Yu-sheng. MAC 2: a multi-hop adaptive MAC protocol with packet concatenation for wireless sensor networks. IEICE Transactions on Information and Systems, 2012, E95-D(2): 480-489.

date： 2013-01-06

JIAO Guo-tai (jgttyx@nuc.edu.cn)

CLD number： TN926 Document code： A

1674-8042(2013)03-0272-04

10.3969/j.issn.1674-8042.2013.03.015