《1 前言》

1 前言

无线自组传感器网络，通常部署在人无法到达的监控区域，通过飞机抛撒等手段将大量无线传感器网络节点随机部署，传感器网络节点根据一定的约束，自组织为一个监控网络。具有节点数量大、多条路由、资源受限、拓扑变化等特点。要实现整个网络快速部署及拓扑变化后的动态重建，最有效的方法就是采用分簇机制，全部节点根据簇头选举和分簇形成机制，形成一个基于分簇的网络结构。这种网络结构可以使网络规模不受限制，可扩充性好，路由和控制开销少，抗毁性强，容易实现移动管理和网络的局部同步。分簇结构网络主要包括簇头选取和分簇形成两个过程。

《2 相关工作》

2 相关工作

簇头的产生是簇形成的基础，分簇路由依赖于簇的结构，分簇算法是 WSN 分簇路由协议设计的关键技术，主要根据如何选择簇头，如何成簇，如何传输数据来考虑设计的。如何节省能量和延长网络生命周期，是考虑的核心问题。目前人们在分簇算法上已经做了大量的工作，文献 [1 ~9] 研究了簇头选择算法、簇形成算法等，并对无线传感器网络基于分簇的网络延迟、节能及网络规模对网络系统寿命、稳定性等方面做了研究。但是研究成果不适合于同种节点随机部署的情况。笔者提出了一种连通可靠度约束的快速成簇算法，算法简单，收敛速度快。第三部分是算法相关概念定义及连通可靠度簇头选举、簇形成算法描述，第四部分对算法进行仿真并对结果进行比较，第五部分是结论部分。

《3 簇头选举算法及簇形成算法》

3 簇头选举算法及簇形成算法

文章的应用目标监测区是人无法到达的区域，通过飞机抛撒等形式部署功能相同的节点组成网络。节点在分簇以前，作用与功能相同，节点按照连通可靠度约束规则组成分簇网络后，节点分为簇头和成员节点，执行不同的功能。

《3.1 相关数据结构定义》

3.1 相关数据结构定义

为了便于算法描述，做如下定义：无向图 G =（V，E，R）表示一个无线自组传感器网络。 其中，V =｛v1 ，v2 ，…，vn ｝表示随机部署的传感网络节点，E表示节点之间的边，如果两节点之间边存在，则两节点是连通的。 E =｛（i，j）：s（i，j）≤2R，i，j  ∈ V ｝，节点的通信半径为 2R 。 各节点在部署之前其功能与作用相同，节点的结构定义为：v =（ID，HD，Type，XYcord，Nbn，CP，Nbs [ ]），分别表示节点的 ID，簇头 ID，节点类型，节点位置，邻居数，连通可靠度，邻居节点详细信息。每个节点有唯一编号 ID(vi ) =i，连通可靠度的定义为：对于成员节点，节点之间的信号强度与两节点在一起时最强信号强度的比值，如式（2）所示；对于簇头节点，表示簇的规模（即此簇内成员的个数，包括簇头）与簇内成员的平均连通可靠度的乘积，如式（3）所示。Type 的取值为 Sensor，NRT，Route，其意义分别为成员节点、临时簇头和簇头，初始化时值为 Sensor，经过初次选择出的临时簇头，Type 值为 NRT，在临时簇头集合内，根据连通可靠度选择算法选择出做为簇头的节点，Type 值变为 Route。 对于任一节点 i，其邻居个数为 Nbn(i )，具体的邻居成员集合信息为：Nbs(i ) =｛ k |s ( k , i )≤2Rs，k ∈ (V -i )｝。 簇头集合为 H =｛vi |vi.type =Route｝，成员节点集合为 S =V -H =｛vi |vi.type =Sensor｝。对于节点为 vi  的簇头，其簇成员为 C(i )。则对于任意的成员节点 v，如果其簇头为 i  则 v  属于 C(i )。

在一次部署 n 个节点组成的无线自组传感器网络中，假设经过簇头二次选择算法得到最终的簇头个数为 Hn，则成员节点数量为 Sn =n -Hn，定义簇的平均规模为：

对于任意两个节点，如果距离较近，则连通可靠度好。为了计算与仿真方便，用节点之间的通信距离来表示连通可靠度。假如节点的通信半径为 ２R，两节点在同一位置，可靠连通度值为 １，则在距离２R 范围内，成员节点与其簇头的连通可靠度表示为：

式（2）中，HD(i )表示节点 i 的簇头，D(i, HD(i ))表示连通可靠度。当节点与其簇头在一起时，其值为 1。

对于某个分簇 C(i )，假设其簇头为 hi，其连通可靠度表示为其所有成员节点的连通可靠度平均值与成员节点的个数的乘积。定义簇头节点的连通可靠度为：

式（3）中， t =NBn(hi ) 是簇 C(i )的成员个数。由式（3）可知，如果一个临时簇头其成员数少，连通可靠度差，则选为簇头的可能性较小，与实际应用一致。

整个网络的连通可靠度 NCP，可用所有成员节点的连通可靠度之和与成员节点数量的比值表示，定义如下：

由式（4）得，如果 NCP 这个值越大，则说明无线自组传感器网络各成员节点与其簇头连通可靠度好，整个网络稳定性、健壮性也越好。

《3.2 基于连通可靠度的簇头选择算法》

3.2 基于连通可靠度的簇头选择算法

基于连通可靠度的簇头选择算法的簇头选择过程分为两个步骤：a. 根据连通性得到临时簇头；b. 从当前的临时簇头，根据连通可靠度约束，得到各个簇头，进一步得到分簇。

3.2.1 基于连通可靠度的临时簇头选择算法

基于连通可靠度分簇的临时簇头选择过程比较简单，并且收敛速度极快。描述如下：

1）节点初始化，开始探测并记录直接邻居，统计直接邻居数，记录直接邻居节点数并记录邻居节点编号 Nbs 等信息。

2）各节点根据自己邻居数与直接邻居的邻居

数目比较，选取直接邻居中 Nbn 值最大的做为自己的临时簇头，并把簇头加入到临时簇头集合中。对于非簇头节点把自己标识为 Sensor，按式（2）计算自己的连通可靠度，对于簇头节点把自己标识成 NRT，按式（3）计算自己的连通可靠度。这样就初步得到临时簇头集合及各簇的成员及连通可靠度、拓扑等信息。

3.2.2 基于连通可靠度约束的簇头选择算法

基于连通可靠度分簇的二次簇头选择算法是在临时簇头选择算法的基础上，根据当前簇头节点的具体信息，再进行一次优化调整的过程。具体步骤如下：

1）如果节点 i 的当前簇头 H(i ) 为临时簇头，并且 H(i ) 相邻的节点中临时簇头或者簇头个数为 0 或 1，表明在它的邻居中只有自己是簇头或者有一个邻居是簇头，把自己标识为簇头，并把它加入到簇头集合 H  中。

2）检索普通节点中，如果邻居节点中没有簇头，则把它邻居中为临时簇头且连通可靠度最大的节点 ID 标识为簇头，并加入到簇头集合 H  中，直到所有的普通节点均有簇头。

3）把节点类型标识仍然为 NRT 的节点，标识为普通节点 Sensor。

4）在簇头集合 H  中，各簇头检测自己的成员是否可以全部“挪”到其邻近的分簇中，如果可以，从簇头集合 H  中删除，并把自己标识为普通节点。

经过以上步骤，基于连通可靠度的簇头选择过程完成，得到了无冗余簇头节点的簇头集合。

《3.3 分簇算法》

3.3 分簇算法

对于任意节点 i，如果其类型为 Sensor，它将选择邻居中连通可靠度最大的簇头节点做为自己的簇头，同时更新簇头 ID 及连通可靠度数据。

《4 仿真设计及比较》

4 仿真设计及比较

假设仿真环境如下：500 m ×500 m，100 个通信半径为 80 m，随机部署 10 次，分别按连通可靠度分簇、最小 ID 算法、最大连接数优化算法进行仿真，并对这四种算法在簇个数(Hn )、簇规模(AHn )、无线自组传感器网络连通可靠度等方面进行比较。3 种算法生成的拓扑图如图 1 所示。

《图1》

图1  在一次部署中,三种算法得到分簇图示

Fig.1  Three different cluster results obtained by once random dispose

在 10 次随机部署中，每次部署分别按三种分簇方法得到 Hn，AHn，NCP 值如表 1 所示。

《表1》

表1  10 次随机部署按三种不同分簇算法得到 Hn,AHn,NCP 的仿真结果

Table 1  Simulation result of Hn,AHn,NCP by ten random dispose with three different clustering algorithms

每一次部署，比较它的分簇规模、连通可靠性得到结果图形化比较，如图 2 所示。

《图2》

图2  三种不同的分簇方法得到的簇规模与簇最大连接度数值比较

Fig.2  Numerical comparison of cluster sacle and clustering connectivity –credibility by three different clustering algorithms

在图 2 中，三种算法分别为：基于连通可靠性分簇算法；基于最小 ID 的分簇算法；最大连接数分簇的优化算法。

从表 1 可知，三种分簇方法中，后两种方法，成员节点并不一定被分到和其连通可靠性最强的簇中。连通可靠度分簇算法和最大连接数优化算法得到的簇头数目较为合理，接近簇头个数占总节点 5 %的比例，且各簇分布比较均匀，但是最大连接数优化算法容易出现单节点分簇，且有所有的簇头均不连通的特点。根据仿真结果，综合比较这三种分簇算法，基于连通可靠度分簇算法，其分簇数目更趋于合理，簇分布均匀，并且网络连通可靠性好，对于保证网络的稳定性与健壮性，减少重构开销来说，有重要的意义。

《5 结语》

5 结语

提出了一种基于连通可靠度的分簇算法，能根据节点随机分布情况，快速的组成一个分布均匀、连通可靠度好的分簇网络。经过对三种分簇算法的仿真比较，基于连通可靠度分簇算法得到的分簇数量较合理，连通性好，基于该方法形成的自组网络具有稳定性强、健壮性好的特点。