黄庆东, 郭 欢, 曹丽霞

(西安邮电大学 通信与信息工程学院， 陕西 西安 710121)

Ad hoc网络是一种典型的无线自组织网络，其拓扑路由管理和维护十分复杂但又至关重要[1-3]。连通支配集(connected dominating set，CDS)是构建虚拟骨干网的一种方式[4]，能简化网络拓扑结构，快速开展路由，减少通信开销[5-6]。通过连通支配集算法实现网络高效管理，广受关注。

基于层次图的连通支配集算法[7]，结合贪心策略，可快速构建支配集，但简化拓扑效果并不明显。剪枝的连通支配集算法(2Rules-CDS算法)利用两种缩减规则改善拓扑结构[8]，其进一步改进(3Rules-CDS算法)[9]，可使所得CDS规模最优，且能解决生成连通支配集时存在的完全NP难问题。不过，这些算法局限于网络单一影响因素，以生成最小连通支配集为目的，忽略了全网负载均衡性。

为改善最小连通支配集负载不均衡问题，本文拟结合加权方式[10]和网络中心性[11]，给出一种基于中心性加权的连通支配集算法。融合多中心性计算网络节点的权值，选取最大者为支配节点，再选其一跳邻居中链路多者为支配邻居，分布式完成支配集构建，并对支配集的连通性进行判断和维护。

1 网络模型和加权公式

1.1 网络模型

Ad hoc网络模型可简单抽象为图论中无向连通图G=(V,E)，V是G的顶点集，表示网络中的节点集(包含|V|=K个元素)，E是G的边集，表示节点之间能直接通信的链路集。图谱论中表征节点连接关系的邻接矩阵定义为A=[akq]K×K，若节点k与节点q相连(q∈Nk，Nk表示节点k的邻居开集)，则元素akq=1，反之akq=0。

1.2 网络中心性加权公式

连通支配集，指网络中一个连通的子网。……