计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2013年
6期
134-137
,共4页
最小连通支配集%支配%连接点%分享度%平均跳数距离%单位圆盘图
最小連通支配集%支配%連接點%分享度%平均跳數距離%單位圓盤圖
최소련통지배집%지배%련접점%분향도%평균도수거리%단위원반도
Minimum Connected Dominating Set(MCDS)%domination%connection point%Share Degree(SD)%Average Hop Distance(AHD)%Unit Disk Graph(UDG)
以节点分享度作为选择分配点的优先级，提出一种最小连通支配集(CDS)求解算法。从根节点开始，将具有局部最大分享度的节点作为支配点，选择连接点与已确定的支配点连通，逐步构造网络的支配树，分析支配树的直径，计算支配树的平均跳数距离(AHD)，从而评价网络的通信成本。实验结果表明，与CDS-BD-C2算法相比，该算法得到的CDS规模较小，且支配树的AHD平均减少12%。
以節點分享度作為選擇分配點的優先級，提齣一種最小連通支配集(CDS)求解算法。從根節點開始，將具有跼部最大分享度的節點作為支配點，選擇連接點與已確定的支配點連通，逐步構造網絡的支配樹，分析支配樹的直徑，計算支配樹的平均跳數距離(AHD)，從而評價網絡的通信成本。實驗結果錶明，與CDS-BD-C2算法相比，該算法得到的CDS規模較小，且支配樹的AHD平均減少12%。
이절점분향도작위선택분배점적우선급，제출일충최소련통지배집(CDS)구해산법。종근절점개시，장구유국부최대분향도적절점작위지배점，선택련접점여이학정적지배점련통，축보구조망락적지배수，분석지배수적직경，계산지배수적평균도수거리(AHD)，종이평개망락적통신성본。실험결과표명，여CDS-BD-C2산법상비，해산법득도적CDS규모교소，차지배수적AHD평균감소12%。
Making point Share Degree(SD) as the priority of selection control point, a new solution algorithm for computing the minimum Connected Dominating Set(CDS) in networks is proposed. Starting from root node, it iteratively selects nodes with maximum share degree in its neighborhood as dominators and some intermediate nodes as connector link to determined dominators previously, and a dominating tree is found gradually. The diameter of the dominating tree is analyzed, moreover its Average Hop Distances(AHD) is calculated in order to evaluate communication costs in networks. Experimental results show that this algorithm can construct smaller CDS than related works, and the AHD is reduced by 12%on average, compared with the CDS-BD-C2 algorithm.
