Abstract: Mobile ad hoc network (MANET) is a centerless packet radio network without the use of any fixed infrastructure. Tremendous attentions have been received because of capabilities of self configuration and self maintenance especially in public safe and disaster recovery situations. Attenuation and interference caused by node mobility and wireless channels sharing, however, weaken the stability of communication links, which makes routing protocol design present nontrivial challenges such as broadcast storm, stale route and delay. The negative impact of wireless routes discontinuity on pervasive communication is alleviated by an effective Self Recovery Routing Game (SRRG) proposed in this study for source-initiated routing protocols by restricting route require zone on intermediate forward nodes according to the solution of optimal exploring equations. The purpose of SRRG is to reduce overhead during route maintenance as well as allowing continuous packet forwarding for fault resilience. NS2 based simulating results indicate that SRRG based on AODV presented in this study achieves much notable improvement for performance of MANET in packet successful delivery rate and total overhead, what is more, obtains much lower average end-to-end delay susceptibility on network capacity and node mobile state simultaneously to improve robustness and survivability.
INTRODUCTION
Mobile ad hoc network (MANET) is a collection of wireless mobile nodes or routers dynamically forming a temporary network without the use of any existing infrastructure or centralized administration for operation in order to allow seamless interconnection for people or equipments in such environments (Sarkar et al., 2008). Each node in MANET enjoys the capacity of sensing and searching for other neighbors (Anquswamy et al., 2008), dynamically ensuring the optimal transmitting route and sending the data packets to any other nodes hop by hop (Forde et al., 2006; Webb, 2007). The factors of node mobility, channel interference and power consumption, however, make the network topology a dynamic one which brings nontrivial challenges to routing design of high performance (Ivascu et al., 2009). An optimal exploration based self recovery model for MANET in wireless link disconnecting situation has been presented in this study, aiming at the deficiency of communication quality turning worse caused by routing instability. The optimal exploring scheme to the next hop node is realized by minimizing cost functional. By defining Hamiltonian function, the exploring function can be simplified as Eikonal equation and transmitting equation, the results of which can be obtained by beam method. To realize such optimal exploration in real communication, a Self Recovery Routing Game (SRRG) by restricting exploring region into a pie slice area pointing to destination node has been proposed in this study. When there are disconnections happening between the source and the destination links, a proper route will be explored for based on a pre-assumed angle from the upstream node without rebroadcasting to the whole network for new routes so as to maintain the data transmission and reduce energy consumption during frequent initialized routing discovery, based on which the survivability of MANET and availability of the routes will be realized effectively.
THE OPTIMAL EXPLORING MODEL FOR SRRG
The optimal exploring theory refers to how to find a target that has already existed beforehand in the best way (Cheng and Heinzelman, 2007), which can help researchers calculate the probability of target being explored successfully corresponding to each allocating method of exploring resource aiming to every region of exploring space (He et al., 2005).
The optimal exploring model: Because of the similarity, the optimal exploration from the Self Recovery (SR) node to the next one, when the link becomes invalid, has been considered in MANET framework. The solution is to find an optimal allocating method about exploring time to maximize the probability of detecting the target successfully, or minimize the cost expectation during a successful perform target detection. At the very beginning of an exploration, the position of the destination node can not be fixed on precisely but can be described by a detection probability function via suitably choosing the variables to maximize probability of detecting the target node at a certain time so as to optimize the exploration to target nodes moving stochastically. Considering characteristics of MANET, the optimal scheme can be achieved by minimizing the cost functional.
Assume X (t)ε Rn is the position of the target node at time t and S (t) ε Rn is the position of SR node at the same time. The joint probability density f (x,t,S) can be defined as follows (Suwansantisuk and Win, 2007):
Obviously, the joint probability density f (x,t,S) approaches to the initial probability density f0 (x) when t is getting close to 0. The detection probability at time t is shown as Eq. 1:
| (1) |
The integral region D in Eq. 1 is where the target node lies, that is to say, D is the subset of exploring space Rn and the probability of target node lying in it is bigger than zero. Exploring equation in 2-D situations satisfied by probability density function is shown in Eq. 2 (Xiao and Tan, 2008):
| (2) |
The survivable probability u (x,t,T,Z) can be defined as:
It is easy to observe that f (x,t,Z) depends on the position of the current node, while u (x,t,T,Z) lies on the initial location of destination node and when t → T, there is u (x,t,T,Z) → 1 to a certainty. Accordingly, the exploring equation in usual case can be described by Eq. 3:
| (3) |
Assume the solutions of Eq. 3 share the same form of Eq. 4, φ (x,y,Z) and gn (x,t,Z) (n = 0,1,2) in which are undetermined unknown functions.
| (4) |
After substituting all-order differentials of f (x,t,Z) into exploring Eq. 3, forms of solutions just accord with that of Eikonal equations and m-transmitting equation shown as Eq. 5 and 6:
| (5) |
| (6) |
Eikonal equation (Li et al., 2008) and transmitting equation (Zhou and Lei, 2007) here are quite similar with asymptotic solutions of wave equations in electromagnetic field which is able to be solved by beam method (Ishkhanov et al., 2008).
Simplification and Solution of Optimal Exploring Equations: In view of Eikonal equation being a first-order nonlinear partial differential equation, Hamiltonian function is defined as Eq. 7. Then Eq. 5 and 6 can be written as Eq. 8:
| (7) |
| (8) |
Differential Eq. 9 can be seen as a beam from the point (x0, p0) in (x,p). If x(t) and p(t) satisfy Eq. 9 and 10 can be obtained by Eq. 6, which illuminates the solution of such equation is , at least on local fields, the solution of Eq. 6. Along the direction of beam generated by Eq. 9, original exploring equation can be simplified as an ordinary differential equation, solving which can get the optimal solution of the original one.
| (9) |
| (10) |
REALIZATION OF SRRG FOR MANET
Taking account into background of our project, AODV protocol (Perkins et al., 2003) is adopted as the original one in this study. First, there is assumption that after a link to the destination node being destroyed or invalidated, there should not be too much difference between reconstructed route and the former one with the purpose of repairing the invalid route locally without informing other nodes to minimize the overhead and affection to other service.
Route discovery and maintenance: When a route is needed to reach a new destination node, a RREQ (Route Request) controlling message to look for a connection to the destination will be broadcast in the whole networks. At the time such message arrives at the destination or at an intermediate forward node with a new enough route to get to such destination, a connection can be established, the process of which is transparent to other nodes in the networks, especially to the source node. Therefore, information like route errors and route changes do not need to be reported to upstream nodes any more during the recovery period. In spite of a different route being set up, in the view of source node, the data flow nearly has not been interrupted so as to realize the SRRG for MANET.
From the math model above, beam method is key point to solve the problem of
obtaining the optimal exploration in minimum cost. The realization of SRRG is
based on such method and extends to a pie slice region in order to increase
success probability. In real communicating situation, directions of received
message can be known, so there is a supposition that information sending direction
is explicit to each other. The nodes set up reference based on geographic direction
as shown in Fig. 1.
| Fig. 1: | Assumption of vector angle sign with North as the reference direction |
| Fig. 2: | Vector angle calculation in a unit model with three nodes |
The number of subscript can be obtained by protocol multi-hop forwarding hop count SEARCHIPCN.
| (11) |
Calculation of route reconstruction: In SRRG model presented in this
study, initial node A will broadcast RRREQ (Route Reconstruction Request) with
vector angle
| (12) |
| Fig. 3: | (a-h) Schematic diagram of SRRG exploring for the next hop node |
When there is a disconnection in an active route, the upstream node will be able to choose local repair if the distance to the destination is not more than maximum repair length MAX_REPAIR_TTL. The upstream node will add 1 to serial number of the destination node and then broadcast a RREQ to it. TTL of RREQ in this study will be set as max(MIN_REPAIR_TTL,0.5x#hops)+LOCAL_ ADD_TLL, #hops in which represents the hop number of unreachable sending nodes (the source nodes). Therefore, such local repair is often unknown to the source and there is always TTL=MIN_REPAIR_TTL+LOCAL_ADD_TTL. Then local repair initial node will wait for an exploring cycle to receive corresponding RREP (Route REPly).
Process of SRRG: Process of exploring for the next hop based on the optimal exploring model being solved by beam method to obtain solution of minimum cost is shown in Fig. 3a-h.
After detecting the connection with node G invalid, node F will send its upstream node A a RRREQ with information of vector between destination and itself to make node A know the vector angle between A and D. Based on SRRG model of route established before, beam method is extended to a pie slice region with node A as vertex and line between node A and D as radius to increase exploring success probability. The vertex angle of this pie slice region depends on node density, energy limitation, node velocity and so on, the value range of which is 0°~360°. When the vertex angle is 0°, the pie slice degenerates to be a right line pointing to the destination node; while vertex angle is 360°, this survivable model expanded to be traditional whole network broadcasting. Obviously the higher vertex angle is set, the larger SRRG reconstructing region covers and the more overhead will be brought in. Any node in this pie slice region will broadcast RRREQ following the same rule if there is no information on reaching the destination node D.
PERFORMANCE EVALUATION
The performance of protocol before and after improved has been compared on ns-2 simulator under LINUX environment (Berkeley, 1998). The default parameter values are set as follows: the nodes are randomly distributed in scope of 1000x1000 m; wireless interface bandwidth of each node is 2 Mb sec-1, emitting signal covers a radius of 250 m. During simulating, several nodes generate service at the same time adopting CBR (Constant Bit Rate) data flow with 512 Bytes as a packet length. Random Way-point mobile model is introduced in this study with a simulating time as 600 sec. Several links will be interrupted artificially in order to validate the efficiency of SRRG and default connection invalid rate is 1 link sec-1. The performance of routing protocol based on traditional protocol AODV (AODV-T) and AODV with SRRG (AODV-S) proposed in this study has been compared by simulating and analyzing the impact of node moving velocity, number of source nodes, Packet Sending Rate (PSR) and Links Invalid Rate (LIR) on Packet Successful Delivery Rate (PSDR), total overhead and average end-to-end delay.
PSDR is the proportion of number of successful delivery packets to number of total sending packets (Begen et al., 2004). Impacts of different parameters on such metric are shown in Fig. 4a and b.
| Fig. 4: | Impact on PSDR by different metrics. (a) Velocities and numbers of nodes and (b) PSRs and LIRs |
| Fig. 5: | Impact on total overhead by different metrics. (a) Velocities and numbers of nodes and (b) PSRs and LIRs |
It can be seen from Fig. 4a that PSDR will begin to descend when the moving velocity and number of source nodes increase, but the descending trend of AODV-S is weaker than that of AODV-T. Statistical results show PSDR of AODV-S will increase by 15.82 and 15.17% respectively comparing with that of AODV-T when the moving velocity is 20 m sec-1 and there are 20 source nodes sending packets. From Fig. 4b we can see the descending trend of AODV-S is much smoother than that of AODV-T with link invalid rate increasing and PSDR decreasing sharply. For example, when there are 5 links fail to connect, PSDR with AODV-T will drop to 70% to make the communication unable to use, while it still remain above 80% with AODV-S.
Total overhead refers to all the information apart from data packets in process of communication establishing from source node initializing the call to source-sink being set up or in process of source nodes that fail to upbuild connections cancel all tries of routing discovery (Kai et al., 2007). Comparisons between AODV-S and AODV-T are shown in Fig. 5a and b. It is easy to understand that the total overhead with these two protocols will both increase when node moving velocity is up and number of source node increases. The curve of AODV-S, however, is much flatter than that of AODV-T, that is to say, it is AODV-S that suits the environment with nodes moving more quickly and larger number of source nodes better.
In real-time service like voice communication, average end-to-end delay (Subramanian et al., 2007) becomes the linchpin, simulation results of which are shown in Fig. 6.
AODV-S strategy is more propitious to the development of real-time service in view of comparisons in Fig. 6a. In Fig. 6b, end-to-end delay of AODV-S is bigger than that of AODV-T when packet sending rate is below 20 packet sec-1, while at 20~25 packet sec-1, they are basically identical, the superiority is embodied when this value is higher than 25 packet sec-1, which speaks volumes for AODV-S is able to support the communication better especially in networks of high dynamic, many source nodes, much data information and frequent link disconnections.
| Fig. 6: | Impact on average end-to-end delay by different metrics. (a) Velocities and numbers of nodes (b) PSRs and LIRs |
CONCLUSION
An effective self recovery model based on the optimal exploring for the next hop node is established in this study aiming at deficiency of communication quality caused by routing instability in wireless communication environment. The optimal exploring scheme is realized by minimizing cost functional to be simplified to the forms of Eiknoal and transmitting equations by defining Hamiltonian functions. Such a first-order nonlinear partial differential equation can be solved by beam method which will be achieved for actual MANET by AODV-based SRRG proposed in this study by calculating the vector angle between the destination and the current node. RREQ is restricted into a pie slice region with line connecting the current node with destination as radius and a pre-assume angle as a vertex angle in order to increase successful exploring probability, the way of which will provide a transparent routing salvage and significantly suppress the overhead in process of routing maintenance. Simulating results indicate that SRRG based on AODV (AODV-S) presented in this study achieves much notable improvement for performance of MANET like PSDR and total overhead and obtains much lower average end-to-end delay susceptibility on network capacity and node mobile state simultaneously to improve robustness and survivability of MANET.
ACKNOWLEDGEMENTS
This study is supported by National Nature Science Foundation under Grant 60432040 and National Key Basic Research Program (NKBRP) under Grant 2007CB310606.