Based on the " Potential " model of the shortest path algorithm in the research and application of wireless sensor network

Cao　Jin-ming　Liu　Yu　Ma　Xiao-hui

【Abstract】This article is based on the research and analysis of Dijkstra and Floyd shortest path algorithm, the shortest path algorithm for Dijkstra and Floyd are widely used for many self-organizing nodes in wireless sensor network. But these algorithms efficiency is low,so I introduce a new "Potential" model based on distributed path algorithm.This "Potential" model will solve the problem of nodes' distributed path addressing, and update the path for the new joining nodes. Reduce the cost of network center node routing computation.

【Key words】Potential algorithm；Distributed；The shortest path.

1.Introduction

Wireless sensor network(WSN)is the result of the cross-development of micro-electronics mechanicalsystem, computer, communication, automation and artificial intelligence [1].WSN has received extensive attention from people because of its features such as low power consumption, low cost, distributed model and self-organization. In recent years, scholars home and abroad have done a large amount of researches on wireless sensor network. Among these studies, the shortest path analysis is a basic one, which has two conventional algorithms: The Dijkstra、Bellman-Ford algorithm solving shortest path problem for single source node and the Floyd algorithm solving shortest path problem for all nodes.

Dijkstra algorithm is the non-negative weight network shortest path algorithm that currently has the most complete theory, while Floyd algorithm is a relatively complete shortest path algorithm among all the nodes. However, Dijkstra and Floyd are both concentrated algorithms, which means that the whole networks path information needs to be known when calculating. So it is unrealistic for the wireless sensor network which has a lot of nodes and should update path information at any time. And the presently used WSN routing protocol like Zigbee is not shortest path algorithm, which leads to a larger path overhead. Furthermore, since their central nodes (coordinating nodes or cluster head nodes) need to manage the communication of the whole network, the overhead will be large, making its survivability relatively low. Under this situation, this article proposed a distributed shortest path algorithm, namely the shortest path algorithm based on “potential”, which well solve the shortest path selection issue for distributed nodes. We applied it into wireless sensor network, reducing the overhead of central nodes, thereby optimizing the network performance.

2.The Shortest Path Algorithm Based on “ Potential”

A.The definition of“Potential”

In the objective physical world, “Potential” refers to a tendency from the high flowing to the low, such as land potential, water potential and electricity potential. In other words, it means layering on the existing difference values according to variable conditions. Here we make some definitions on several nouns appearing in this paper.

Definition 1:“Potential base point”: The standard point of layering.

Definition 2:“Potential base point set”: The set of selected potential base points is called potential base point set, denoted as Z.

Definition 3:“Potential value”: The hop number or overhead from a node to “potential base point” in network topology undigraph is called potential value, denoted as, where x means using x node as potential base point.

Definition 4:“Potential value set”: The set of “potential value” from node to different potential base point, denoted asωm=（ βm1，βm2，βm3，…βmn, where n is the total number of potential base points and m indicates the node name.

Definition 5:“Potential description”: Describing the topology of undigraph using “potential value set”.

B. Potential description for network topology

MSSTATE _L- RWPAN protocol stack has the network topology structure that is a typical hierarchic network. Its hierarchic model is shown in the following figure.

Fig.1Hierarchic Draft of Msstate _L-RWPAN Protocol

With the above hierarchic model, we can regard the coordination node as potential base point with a 0 potential value and then obtain the potential values of other nodes in the whole topology. In figure 1, the potential values of node “A、B、C、D、E、F” are all 1, and node “G、H、J、K、L、M” all have potential value 2.

In order to determine the shortest path from layering or potential, multiple potential base points need to be adopted.

Fig.2Nodes Topology Draft

Taking the topology of figure 2 for example (here the cost of each connected line is assumed to be1),we choose A and D (two different potential base point) to conduct the potential description for the topology of the figure, namely Z={A,D}. Here we pretermit that the cost of each path is 1, and the nodes set is M={A,B,C,D,E,F,G,H}.

The “potential value” set using node A as potential base point is:

A(β)={The potential value of X is equal to the set of , X M}. Hence “potential value” set for figure 2 will be:

A(0)={A}; (Nodes set with base point A and potential value 0)

A(1)={F, B}; (Nodes set with base point A and potential value 1)

In the same way,

A(2)={D,E,H};={G,C}

Taking Node D as base point,then from the figure above it can be obtained that the “potential value”set is

D(0)={D};??A(1)={F, G};??A(2)={A, E};

A(3)={B,C};??A(4)={H}; (Here it is the same as node A)

According to what is stated above, A is among the“potential value” set of??D(0)and??A(2),hence node As potential value set is:

ωA=（0，2）；(Namely that the potential values from node A to base point A and D is respectively 0 and 2)

In a similar way, the potential value set of each node can be obtained as follows:

ωB=（1，3）；ωC=（3，3）；ωD=（2，0）；ωE=（2，2）；ωF=（1，1）；ωG=（3，1）； ωH=（2，4）.

The potential value set acquired by undigrapgh topology has achieved the potential description of network topology structure.

We give the steps of “potential” based algorithm in this paper using figure 3.

Fig.3Undirected Graph with Weights

Of which the specific steps are as follows:

Step 1:Select potential base point based on network topology structure.

Step2:Potential base points flood, each node of the whole network obtain their own potential value set.

Step 3:Each node automatically addresses according to potential value set.

C.Flooding algorithm used to determine the potential value in “potential” algorithm.

Flooding is a kind of data flow transmission technology between communication equipments, where the data flow received by a interface will be send out from all the interfaces except the one which received it. The flooding in this article means “potential” flooding, which determines the directions and range of flooding according to the size of potential value, thereby making the flooding redundancy of network reduce greatly.

The flow chat of “potential” based flooding algorithm is shown in figure 4:

Fig.4Flow Chat for “Potential” Based Flooding Algorithm

Compared with the improved Bellman-Ford algorithm with queue mode, namely SPFA（Shortest Path Faster Algorithm, the aforementioned flooding algorithm has the same time complexity O(k ), where k indicates the average number of entering of all the summit nodes ( it can be proved that k is generally smaller than 2) and is the side number of the graph of network construction. The different lies in that SPFA is a centralized path information algorithm while the potential flooding in this paper is a distributed algorithm using the node potential value to determine reduced redundancy. On average, each nodes calculating time complexity will be O (k/n) (Where n denotes the nodes number in network).

In accordance with the flooding algorithm above, the 3 potential nodes potential values of the 7 nodes within figure (3) can be acquired. （Z={1,2,7}）

ω1=（0,2,5）;ω2=(2,0,6);ω3=(5,3,5);ω4=（3,1,5）;ω5=(1,3,4);ω6=(5,3,5);ω7=(5,6,0);

D.“Potential” based routing selecting algorithm

Suppose that the “potential value set” of a node M obtained by “potential” flooding algorithm is ωm=（βm1，βm2，βm3，…βmn,and the “potential address” of another node N obtained by “potential” flooding algorithm isωn=（βn1，βn2，βn3，…βnn. Here node M is assumed to reach to nodes set?mby one step, and the one-step reachable nodes set for node x is?n.

The routing path selection algorithm from node M to N is shown in figure 5.

Step 1: ResolveY∈?m(Y is the one-step reachable node of M), it meets

a

β-β

+aβ

-β

+...aβ

-β

min.

Wherea，a，…aare the weights of potential base points, and in this articlea，a，…aare all supposed to be 1.

Step 2: ResolveX∈?y(X is the one-step reachable node of Y), it meets

a

β-β

+aβ

-β

+...aβ

-β

min.

Fig.5“Potential” Based Routing Path Selection Algorithm

During the process of path selecting, the first time recorded node Y and the follow-up recorded node X are the selected middle path nodes from M to N. Thus the path selecting from M to N has been accomplished.

For example, in the topology of figure (3),the shortest path from node 4 calling on node 6 is （Z={1,2,7}.

Firstly we know that the potential value of node 6ω6=（β61，β62，β67)and the potential value of node 4ω6=（β41，β42，β47); And the reachable nodes for 4 is 2 and 7 ,ω2=（β21，β22，β27)ω7=（β71，β72，β77)

(According to figure 3 and the above description, there will beω2=(2,0,6)、ω6=(2,4,3)，ω7=(5,6,0);) Since

|β21-β61|+|β22-β62|+|β27-β67|<|β71-β61|+|β72-β62|+|β77-β67|

So the next hop of selection is node No.2 instead of node No.7 with a smaller weight. Through this way, the shortest path from 4 to 6 will be in turn selected as 4->2->3->6.

From section C, each nodes time complexity in our potential flooding algorithm is O(k /n), while the time complexity of each node in this sections potential set comparison is O(k), hence the time complexity of our proposed algorithm should be O(k /n+k). It can be proved that k is generally less than or equal to 2[6].

E.Applications of wireless sensor network

Currently in wireless sensor network, there are many routing protocols, of which Zigbee protocol is a widely applied one. The network construction of Zigbee is easy and fast. Yet, because it does not go along the shortest path during communication, even if when two nodes are very near with each other, they still need to realize the communication through routing nodes or even coordinating nodes. Simultaneously, the overhead of coordinating nodes is large, thus it will lead to a shorter network life circle. So we added “potential” based path algorithm into wireless sensor network, not only reducing the communication overhead, but also making each node in the network share the whole overhead in communication.

Fig. 6Wireless Sensor Nodes Distribution Draft

Figure 6 is the potential flooding simulation draft of the random distributed 100 nodes with the 500m 500m area. Potential value sets are in the brackets. A,B,C are chosen as potential base points, namely Z={A，B，C}；

F.Nodes “potential value set” updating

In our network constructed by potential value set, the potential value set is not invariable. For instance, when a new node joins in the network or a node exit,it will change.

Next we make some discussions on the above mentioned two situations.

2.1 New node joining in the network

When a new node joins in the network, the node traverses its reachable nodes to get its minimum potential value. Then,addP(Single hop path overhead) to it to get the new nodes “potential value”.In the following, traversal the one-step reachable nodes to find the node whose potential value isPlarger than its own, sending out updating command to make its potential value become the sum of new nodes potential value and path overhead, thereby successively update its new reachable nodes. Thus the potential value set of the whole network is updated with the minimum cost, which means the routing information of the whole network is updated.

2.2 Network with node exiting

Because of the exiting of nodes, some nodes “potential value” may be relatively small, leading to failed communication. When communication failure appears, launch communication nodes to acquire new potential value set like the newly joined network nodes, and simultaneously update the networks potential value set like the new nodes.

3.Simulation Experiments and Analysis

A.Simulation environments

This paper simulated the algorithm under matlab environment. The nodes are randomly distributed and the node density is 1 node/25 square meters. Under this condition, we simulated the routing hops number (each hops overhead was assumed to be 1 and the weight is 1). The transmission distance is 100m.

B.Simulation Results

Figure 7 is the potential flooding addressing simulation draft of 100 randomly distributed nodes within a 500m 500m area.

The result of addressing the most distal two nodes A and B in figure (6) is shown in the draft below.

Fig.7Nodes Potential Addressing Draft

In theory, the minimum hops between the communication of two nodes is

N=ceil() 1-1

Where ceil is top integral function, d indicates the distance between two nodes and r indicates the radius of single hop communication.

In the simulation experiments, we adopted the random nodes distribution with node density of 1 node/25 square meters, and the whole networks average hops are acquired as figure (7) shows.

Fig.8Comparison of Simulated Routing Number and Theoretical Value

From figure (8)it can be seen that the bottom curve means the theoretical hops of shortest path of potential. The second curve means the hops of “potential” based routing. And the top curve means the theoretical average hops of Zigbee after the whole network communicating once. So it is clear that the “potential” based routing hops is only a little more than that of theoretical shortest path. However, for the theoretical average hops of Zigbee, our algorithm has almost triple efficiency improvement on average communication hops.

4.Conclusion

This article proposed the “potential” based shortest path addressing algorithm aiming at the shortest path issue in wireless sensor network. This algorithm has effective performance improvement on routing hops for wireless sensor network or other networks with many nodes. The advantage of our algorithm is that it can achieve the real-time path selection of dynamic network and meet the self organization and distribution requirements of wireless sensor network.[科]

【References】

［1］Limin Sun，Jianzhong Li，Yu Chen. Wireless Sensor Networks [M].Bei Jing：Tsinghua University Publishing House,2005.(In Chinese).

［2］Hwan Il Kang, Byunghee Lee,Kabil Kim.Path Planning Algorithm Using the Particle Swarm Optimization and theImproved Dijkstra Algorithm.IEEE，2008.376:1002-1004.

［3］Guiping Wang,Yan Wang,Jiachen Wang.Graph theory and application of the algorithm is realized[M].Beijing：Beijing Publishing House,2011.(In Chinese).

［4］IEEE Std 802.15.4TM.Part 15.4:Wireless Medium Access Control (MAC) and Physical Layer (PHY)Specifications for Low-Rate Wireless Personal Area Networks (LR-WPANs)[S].2003.

［5］Dr. Robert B.Reese.A ZigbeeTM-subset/IEEE 802.15.4TM Multi-platform Protocol Stack[E].2006.

［6］Fanding Duan.About the shortest path algorithm SPFA fast. Southwest Jiaotong university press,1994(2):207-212(In Chinese).