Research On The Method Of Data Transmission In MANET Based On Percolation Theory

A mobile ad hoc network (MANET) is one consisting of a set of mobile hosts which may communicate with one another and roam around at their will via multi-hop wireless links. No base stations are supported in such an environment. Just for these features above plus the characteristics of the MANET itself, it is crucial to take topology control in MANET.So far, there are two main methods for topology control in MANET, one is computational geometry methods, one is probability analysis method, percolation theory is one of the probabilistic analysis.Broadcasting is a fundamental and important communication primitive. Of all broadcast algorithms the simplest and most popular one is flooding, with which nodes rebroadcast the messages to their one-hop neighbors as long as they receive the messages for the first time. However, flooding can cause broadcast storm problem. The probabilistic scheme and distance-based scheme are both solutions to relieve this problem.In this paper, the percolation theory has been applied to optimize the broadcast schemes in MANET, we propose two new optimal algorithms as follows: an optimized probabilistic broadcast for mobile ad hoc networks with percolation theory (OPBP) and a distance-based broadcast for mobile ad hoc networks with percolation theory (DBPT).we added the directional rebroadcasting to the forwarding algorithms, nodes rebroadcast the message with probability p which is the critical probability threshold. It is proved by simulation that this method not only improved the low reachability in large-scale sparse networks but also greatly enhanced the effective utilization of node energy.Percolation theory is used to analyze the cause of the phase transition which also can be called the occurrence of percolating. We use two models to analysis this phenomenon: square grid model and fixed radius model. In square grid model, nodes can only communicate with others horizontally and vertically. When the source node the one lies in the center of the square grid broadcast the messages, in order to guarantee all of other nodes can receive it, it needs to broadcast m2 messages. It can be mapped the site percolation. And it is merely suitable for the nodes whose neighbor nodes are four. In comparison, the fixed radius model is more adaptable in MANET. In this model, nodes are deployed according to the Possion distribution in the target region. Edge lij means node i and node j are connectable. The source node quits to forward the messages with probability 1-p other than broadcast the messages to all of its neighbors. In percolation theory, it can be described as the percolating stops. It can be mapped to the bond percolation. The algorithm OPBP is proposed based on the fixed radius model. To compare with the square grid model, nodes in fixed radius model also have four neighbors around them. This number"four"is within the range of the magic number under Gilbert's guess. Even in the large-scale sparse networks, it is easy to satisfy this request.In the algorithm OPBP, it is mapped to the bond percolation. Through the proof, it is showed that there exists the critical threshold which can make the networks exactly connectable. The bond percolation is indeed a directional idea, nodes rebroadcast the messages with the critical probabilistic threshold and not to all of the neighbors like that in the traditional probabilistic scheme but do as it is described in the algorithm OPBP step by step, pick out some rebroadcasting nodes and then rebroadcast directionally. In the algorithm OPBP, the transition range of nodes are divided into four sectors, and supposed being"unoccupied". Firstly ,define the smallest range of one node as the initial transition range, rise the transition range gradually, search each sector with the critical probabilistic threshold p , when at least one node can be found ,mark the sector"occupied", loop these steps until all the sectors are occupied or nodes have reached its max transition range. The traditional probabilistic scheme can be mapped to site percolation. Under the same network topology or nodes in the same degree, the critical threshold probability P of bond percolation is smaller than that of site percolation. This in some degree describes there are fewer nodes involved or open bond when rebroadcast directionally than omnidirectionally. In other words, it realizes to save nodes energy and to prolong the lifetime of MANET. In addition, there are no special requirements about the networks size, node number and node distribution in algorithm OPBP, and it performs better in large sparse networks. Through the simulation with NS2, we have confirmed the algorithm OPBP's correctness and superiority for one more time.In the algorithm DBPT, we redefine the distance threshold D of the traditional distance-based scheme, transfer it into the expected additional coverage(EAC),the fewer the EAC is ,the more the transition range of two nodes overlaps, the more often messages collide .we divide the received nodes'transition range into eight sectors ,and then divide each sector into two ,each bisector cross with the source node's transition range ,mark each cross-point, connect these eight cross-points to the received node, the length of each is d, d is a variable. Let the rebroadcast probability Pi related to the distance d, when d is larger than the transition radius, it shows that these two nodes are too near as to quit the rebroadcasting. In this way, we make nodes which are different distance from the source nodes with different Pi and redefine the formula for calculating Pi. All of above we conclude that Pi is capable of adjusting to the node density.In chapter V, we raise the routing algorithm with percolation theory --AODV with percolation theory (P-AODV).The core idea of it is to reduce the overhead when sending the RREQ packet during the route discovery process. In AODV, the RREQ packets are forwarded by nodes via flooding, which can give rise to signal collisions and packet loss. We add the idea of percolation to forwarding the RREQ packets that makes the RREQ packets forwarded directionally with critical threshold probability P. P-AODV algorithm is simple and easy to understand, in particular, it is not complex to simulate, and needed to mention that it illustrates better of its performance than AODV .These three new algorithms are based on the percolation theory and simulated by NS2. This is an attempt and exploration to apply percolation theory into MANET.