一种考虑障碍物的ad hoc网络分簇算法

现有的很多ad hoc网络分簇算法都没有考虑实际的物理环境因素，如地球表面的各种障碍物。而障碍物既阻碍节点移动，又限制无线传输，对分簇结果影响很大，可能会导致簇的尺寸过小，簇的数目较多，从而引入大量的通信和计算开销。结合Voronoi图，在最小ID启发式算法的基础上，提出一种考虑障碍物的分簇算法。通过设置备用节点，可以解决障碍物环境下ad hoc网络的连接性问题。最后通过实例仿真对该算法和最小ID算法进行性能比较和评价。

A CLUSTERING ALGORITHM FOR AD HOC NETWORKS TAKING ACCOUNT OF OBSTACLES

Most of the existing clustering algorithms for ad hoc networks do not take into account the real physical environment factor,such as various obstacles on the surface of the earth.However,these obstacles are utilized to both restrict node movement as well as wireless transmissions and therefore could have significant influence on the clustering results.This may result in the small size of the cluster and a large number of clusters,but more clusterheads will lead to high communication and computation costs.By combining the features of the Voronoi graph,this paper proposes an obstacle clustering algorithm (OCA) that enables the inclusion of obstacles based on Lowest-ID heuristic algorithm.We try to address the problem of connectivity in ad hoc network with obstacles by placing spare nodes in appropriate place.Eventually,simulation experiments are conducted to evaluate and compare the performance of OCA and Lowest-ID heuristic algorithm.