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

A CLUSTERING ALGORITHM FOR AD HOC NETWORKS TAKING ACCOUNT OF OBSTACLES

作　　者：吴迪[1] 屈岩[1] 陈晓川[2] 

机构地区：[1]大连理工大学计算机科学与工程系,辽宁大连116024 [2]东华大学机械工程学院,上海200051

出　　处：《计算机应用与软件》2006年第9期16-18,共3页Computer Applications and Software

基　　金：国家"八六三"高技术研究发展计划基金项目(2003AA712032)

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

关 键 词：Ad HOC网络 分簇算法 障碍物 VORONOI图 最短路径 

分 类 号：TP393.01[自动化与计算机技术—计算机应用技术]