The Implementation Of Hierarchical Distributed HSLS Routing In Large-scale Ad-Hoc Network

The Routing Protocol of Ad Hoc network was a popular research theme in the past serval years, the recent studies on the application such as intelligent sensor network are more focus on the scalability of the network. With network size growing, the existing routing algorithms have the problem of high routing overhead and low scalability. In order to keep the good communication of large-scale network we need to reduce the costs and optimize the performance of network. But there has an important problem: which routing protocol will performance good when consider network scalability and routing overhead?Link stated routing algorithms usually adopt two schemes to reduce routing overhead, which is the coverage-controlled broadcasting scheme and the efficient broadcasting scheme. HSLS routing algorithm uses the coverage-control technology, by reducing the TTL of link state update message to control the distance. However, coverage-control technology will lead to suboptimal routing problem, which unable to further reduce the overhead. In order to solve this problem, the literature[15] redefine the total overhead of routing algorithm, introducing sub-optimal routing overhead.We combine the strengths of the coverage-controlled broadcasting scheme and the efficient broadcasting scheme, and proposed a hierarchical distributed HSLS routing algorithm based on virtual backbone. The protocol seamlessly integrates a MCDS based construction scheme into the link state routing algorithm, while an expanding-ring search scheme is also adopted. Compared with HSLS the new algorithm using virtual backbone to reduce the broadcast overhead and limit LSU forward. The introduction of VB can tolerate more sub-optimal routing overhead and reduce the total overhead. Even through maintenance the VB will adding some overhead but this technology has a better performance in broadcasting message controls.Considering the influence of the virtual backbone network,we calculated the total cost of VB-HSLS and calculated the minimum broadcast interval of HSLS and VB-HSLS. By using MATLAB We proved that under the same conditions VB-HSLS can significantly reduce the total cost of the algorithm compare with HSLS.When the the condition of network diameter D under 2 ?D ?500, the differenceunder of minimum total cost under relaxed condition and integer solution condition is always less than 0.743%. At the same time, we proved that the total cost doesn’t grow with the network diameter and grow fast when network density increase.At the end of this paper we proposed the implementation of VB-HSLS protocol based on the research of VB-HSLS in theory, and we verify the feasibility of hierarchical distributed HSLS routing algorithm under Linux operating system. We set up the experimental platform for functional testing of the implementation of the scheme, including static and dynamic network scene. Experimental results show that the protocol is feasible which has a good performance and the algorithm of static and dynamic network.