分布式生成树中限制搜索半径的定位算法研究

Research on search radius limited location algorithm in distributed spanning tree

在分布式生成树(DST)中,针对限制TTL的DST定位算法不能有效地降低搜索时间和网络带宽使用的问题,提出了一种基于搜索半径限制的定位算法,并给出了确定搜索半径的依据.在资源均匀分布的DST中,满足条件的搜索半径可以确保搜索请求以高概率成功定位到符合条件的资源,减少了网络带宽的使用,缩短了资源定位时间。通过数学分析和实验仿真,说明基于搜索半径限制定位算法的网络带宽使用和搜索时间与网络规模无关,算法的时间复杂度为常数阶,其性能优于限制TTL的DST定位算法。

In the distributed spanning tree（DST）,to resolve the problem that the DST location algorithm with TTL limited can not effectively reduce the searching time and the network bandwidth usage,we propose a location al-gorithm based on search radius and also describe a basis for determining the search radius.In the DST with resources uniformly distributed,the qualified resources can be successfully located by using the algorithm with satisfied search radius,so the network bandwidth usage and searching time can be reduced.Through the mathematical analysis and simulations,the results show that the network bandwidth usage and searching time of the location algorithm with search radius limited are not related with the network size,the time complexity of which is constant order,and whose per-formance is better than the DST algorithm with TTL limited.