基于K-means聚类和蚁群算法的多级异构无线传感器网络分簇路由方法

摘要

本发明公开了提出的一种基于K-means聚类和蚁群算法（ant？colony？optimization,？ACO）的分簇路由协议（K-means？clustering？and？ACO？optimal？routing，即KCAOR协议）。在多级异构无线传感器网络环境下，首先由最优簇首个数公式确定监测区域内的最佳簇域数量，然后采用K-means聚类方法将网络中的节点自然聚集成相应的簇域；提出簇域均匀优化策略，实现网络能耗的均匀分布，再根据簇内节点的剩余能量值选举簇首；采用蚁群算法确定簇首与基站之间的多跳最优路由，均衡簇首之间的能量消耗；在数据传输的末轮，通过增加节点状态包，基站能够实时掌握网络的运行情况，实现协议的优化。本发明能够有效均衡网络的能量消耗，延长生存时间，提高无线传感器网络的性能。

说明书

技术领域

本发明涉及网络路由协议，具体涉及多级异构环境下的无线传感器网络分簇路由方法。

背景技术

无线传感器网络(WirelessSensorNetworks,WSNs)由大量随机分布在监测区域内的传感 器节点和基站组成，已广泛应用于国防安全、工业控制、环境监测、抢险救灾和科学探索等 方面，根据节点不同的感测能力、通信能力、计算能力和初始能量，可以分为异构网络和同 构网络两种，异构网络由多种不同性能的节点组成；同构网络则由相同性能的节点组成。传 感器节点通常采用电池供电且大多工作在环境恶劣或者人类不容易到达的地方，因此无线传 感器网络协议的首要目的是提高能量的利用效率。近年来，在研究人员提出的大量新型路由 协议中，层次型路由协议被公认为最适合于实际无线传感网的应用。其基本思想是先将网络 划分成多个簇域，每个簇域通常由一个簇首和若干成员节点组成，成员节点负责采集数据并 发送给簇首，簇首融合数据再发送到基站。

LEACH协议是一种低能耗自适应分簇路由协议。在该协议中，先以循环的方式随机选择 簇首节点，每个传感器节点再根据接收到的簇首信号强度，加入到信号最强的簇域；每个簇 由簇首节点负责收集所有成员节点的信息并做出相应的处理，并由簇首负责协调成员节点之 间的工作。LEACH协议通过轮换簇首的方式使整个网络的能耗平均分配到每个传感器节点 上，达到延长网络生存时间的目的，但该协议主要针对同构网络，当运行到异构网络中时， 因传感器节点性能存在差异而导致协议的性能大大降低。

SEP协议根据初始能量将网络中的无线传感器节点分为两类，高级节点和普通节点，高 级节点的初始能量高于普通节点，并将节点的剩余能量和加权选择概率作为簇首选举的依据。

DEEC协议是一种适合多级异构网络的分布式能量有效成簇协议。该协议充分考虑了多 级异构网络环境下，各个节点能量之间的差异性，通过所有节点轮流成为簇首达到均匀消耗 能量的目的,而选举簇首节点的概率与节点当前剩余的能量直接相关。每个节点成为簇首节点 的轮数根据其初始能量和剩余能量的差别而不相同，即簇首轮转周期适应节点的能量变化。 具有较高初始能量和剩余能量的节点比低能量节点有更多的机会成为簇首节点。DEEC协议 通过采用这种考虑异构节点配置的成簇算法来延长网络的生存时间，特别是网络的稳定周期。

现有协议存在的问题：

1)在成簇过程中通常采用先预测节点能量使用情况来计算节点的概率门限值与节点自身 产生的随机数进行比较来确定簇首及建立簇域。通过随机数与预测能量来选取簇首和建立簇 域的方式存在大量不确定的因素，从而导致簇首数量不稳定和簇域分布不均匀，使网络能耗 较大，降低了网络的能量利用效率和生存时间。

2)簇首与基站通信时使用单跳的方式，会使离基站较远的簇首能量消耗过快；有些协议 采用了多跳方式，但由于路由选择不恰当，限制了其降低能耗的效果。

发明内容

针对现有协议存在的问题，本发明提供一种基于K-means聚类和蚁群算法(antcolony optimization,ACO)的多级异构无线传感器网络分簇路由方法(K-meansclusteringandACO optimalrouting，即KCAOR协议)。

本发明的技术方案如下：

一种基于K-means聚类和蚁群算法的多级异构无线传感器网络分簇路由方法，包括：

基于K-means聚类的无线传感器网络分簇；

基于蚁群算法的无线传感器网络簇间路由选择；

在数据传输阶段，簇首采用单跳和多跳相结合方式传输数据，同时在数据传输的末轮， 通过增加节点状态包的方式，基站能够完整掌握全网节点的实时状态信息。

所述的基于K-means聚类的无线传感器网络分簇方案，具体步骤如下：

(1)确定簇域数量：由DEEC协议的最优簇首数量计算公式(1)确定无线传感器网络中 簇首的最优个数，作为网络的最优簇域数量K。

$K_{opt}=\frac{\sqrt{N}}{\sqrt{2\pi }}\sqrt{\frac{{ϵ}_{fs}}{{ϵ}_{mp}}}\frac{M}{{d^2}_{toBS}}---\left(1\right)$

其中，N为无线传感器节点个数，M为正方形监测区域的边长，d_toBS为簇首与基站之间 的平均距离，ε_fs和ε_mp为无线传感器发送数据时的能耗参数；

(2)聚类算法分簇：从全网节点中随机选取K个节点作为每个簇域的初始质心，计算 其余节点与各初始质心的距离，将节点划分至最近的簇域中。更新所有簇域的质心，并计算 K-means聚类算法的准则函数，若不收敛，则对全网节点重新分簇，更新质心，直至准则函 数收敛；

(3)均匀簇域负荷：确定算法的迭代次数NC_max，根据簇域最优成员节点数量公式(2) 确定各个簇域的最优成员节点数量Num_opt。对成员节点数量小于Num_opt的簇域进行拆解，成 员节点数量大于Num_opt的簇域进行拆分，直到算法的迭代次数达到NC_max；

${\mathrm{Num}}_{opt}=\mathrm{mod}\left(\sqrt{2\pi N}\sqrt{\frac{{ϵ}_{mp}}{{ϵ}_{fs}}}\frac{d_{toBS}^2}{M}\right)---\left(2\right)$

(4)簇首选择：对每个簇域内的节点剩余能量值进行比较，选择剩余能量值最大的节点 作为本簇域的簇首。

所述的基于蚁群算法的无线传感器网络簇间路由选择方案，具体步骤如下：

(1)根据各节点之间的距离长度确定每条路径的启发因子η_ij，设置算法的迭代次数 NC_max以及其他一些参数；

(2)每个簇首产生k个探测分组，并将这些探测分组随机发送至各个簇首，探测分组每 经过一个簇首便将该簇首记录到自己对应的禁忌表中；

(3)每个探测分组依据概率公式(3)确定下一个待访问的簇首，直至探测分组抵达基站；

to_visit＝N-Tabu_k(4)

其中，N表示节点集合，Tabu_k表示第k只蚁群已经过的节点集合即禁忌表，to_visit为待 访问的节点集合即候选集；τ_ij(t)表示t时刻路径ij上的信息素量；η_ij为路径ij的启发因子，我 们取节点i与j之间距离的倒数；α、β分别表示每条路径上信息素和启发因子的相对重要程 度；

(4)待所有探测分组到达基站后，分别从每个簇首的探测分组中选出游历路径最短的分 组，对这些探测分组所经过的路径上的信息素进行更新；

(5)回到(2)继续进行，直至算法的迭代次数达到NC_max。

所述的在数据传输阶段的步骤：在数据传输阶段，每个簇域内的成员节点按照各自分配 到的传输数据的时间点向簇首发送数据；簇首根据与基站的距离确定其数据传输方式(单跳 或多跳)；在数据传输的末轮，每个节点在发送数据包的同时增加一个包含本节点当前剩余能 量、所属簇域、ID号以及位置等信息的节点状态包。

本发明可以获得如下有益效果：

(1)充分考虑各网络节点能量的差异性，均衡网络的能量消耗。

(2)提高能量的使用效率，延长网络的生存时间。

(3)提高网络的稳定性。

附图说明

图1是本发明无线传感器网络节点的随机分布示例图；

图2是本发明所述基于K-means聚类的无线传感器网络分簇方案的簇域分布图；

图3是本发明所述基于蚁群算法的无线传感器网络路由选择方案的簇间最优路由图；

图4是本发明所述的KCAOR协议与LEACH、SEP和DEEC协议的网络生存时间对比 图；

图5是本发明所述的KCAOR协议与LEACH、SEP和DEEC协议的网络能量消耗对比 图；

图6是本发明所述的KCAOR协议与LEACH、SEP和DEEC协议的数据包总数对比图；

具体实施方式

下面参照附图和实施例对本发明做进一步的详细描述。

本发明提出的基于K-means聚类和蚁群算法的多级异构无线传感器网络分簇路由协议采 用与DEEC协议相同的网络模型，协议的运行过程分为三个阶段：簇域的创建、簇间路由的 选择和数据传输。

1.多级异构网络模型构建

假设N个拥有不同初始能量的传感器节点均匀地部署在边长为M的正方形区域内，传感 器节点周期性地采集数据且具有如下性质：

(1)网络中的传感器节点各自具有唯一的标识号(ID)，节点不可移动；

(2)基站位置固定，能量不受限制，且无线发射范围覆盖整个网络；

(3)传感器节点的初始能量在闭区间[Eo，Eo(1+αmax)]内随机分布，如图1所示，在协议 运行过程中不能补充，各节点能够随时获知自身当前的剩余能量且具备一定的数据处理能力；

(4)网络的通信链路对称。传感器节点可以通过无线信号强弱，计算出与发射节点的近 似距离，节点同时可以根据与接收方的距离调节发射功率。

协议的能量模型，假设某个节点发送l比特信息，发送距离为d的过程中，发送端的能 量消耗表达式为：

$E_{Tx}(l,d)=\left(\begin{array}{c}{\mathrm{lE}}_{elec}+{\mathrm{lϵ}}_{fs}{d}^2,d<d_0\\ {\mathrm{lE}}_{elec}+{\mathrm{lϵ}}_{mp}{d}^4,d\ge d_0\end{array}\right)---\left(1\right)$

其中，d₀为数据通信过程中的距离阈值，当节点的发射距离小于阈值d₀时，节点能量消 耗采用自由空间模型，反之，则采用多路径衰减模型；E_elec表示接收电路或发射电路运行时 消耗的能量；ε_fsd²和ε_mpd⁴为放大器消耗的能量。则单个节点接收l比特信息时消耗的能量表 达式为：

E_Rx(l)＝lE_elec(2)

2.簇域的创建

2.1聚类算法分簇

最优簇首数计算公式：

$K_{opt}=\frac{\sqrt{N}}{\sqrt{2\pi }}\sqrt{\frac{{ϵ}_{fs}}{{ϵ}_{mp}}}\frac{M}{{d^2}_{toBS}}---\left(3\right)$

其中，N为无线传感器节点个数，M为正方形监测区域的边长，d_toBS为簇首与基站之间 的平均距离，ε_fs和ε_mp为无线传感器发射能耗的参数。

平方误差函数：

$D={\Sigma }_{i=1}^n\left[{\min }_{r=1...k}d{(m_i,c_r)}^2\right]---\left(4\right)$

其中，n表示网络中的节点数；k表示网络中的质心数；d(m_i,c_r)表示网络中的节点i到质 心r的距离，由欧式距离函数确定。

本发明中的K-means聚类分簇算法，先由公式(3)计算出簇首的最优数量作为网络的初始 节点数K，再从全网节点中随机选取K个节点，作为每个簇域的初始质心；然后对剩余的其 它节点，计算其与初始质心的距离，并划分到最近的簇域中，重新计算并更新每个簇域的质 心；最后计算准则函数，本发明采用平方误差函数作为K-means算法的准则函数，如公式(4) 所示，若准则函数不收敛，则根据新的质心位置重新组建簇域，否则终止算法的迭代并输出 簇域的分布情况Cluster_i和成员节点数量Num_i(i＝1,2,…,K_opt)。

2.2簇域均匀策略

定义1：小簇域。本发明将多级异构网络中簇域内成员节点个数Num_i<Num_opt(Num_opt由公式 (6)确定)的簇域称为小簇域，记为Cluster_min_i(i＝1,2...,C_Num_change，其中C_Num_change为小簇 域的数量)。

定义2：大簇域。小簇域拆解后，对余下簇域按簇内成员节点个数进行排序，本发明将排序 结果中最大的C_Num_change个簇域称为大簇域，记为Cluster_max_i(i＝1,2...,C_Num_change)。

通常情况下，一个簇首及若干个成员节点组成一个簇域，则每个簇域内的最优成员节点 个数为：

${\mathrm{Num}}_{opt}=\mathrm{mod}\left(\frac{N}{K_{opt}}\right)---\left(5\right)$

将公式(3)代入(5)，可得：

${\mathrm{Num}}_{opt}=\mathrm{mod}\left(\sqrt{2\pi N}\sqrt{\frac{{ϵ}_{mp}}{{ϵ}_{fs}}}\frac{d_{toBS}^2}{M}\right)---\left(6\right)$

本发明提出的簇域均匀策略，是先由公式(6)计算确定簇域的最优成员节点个数Num_opt， 与各簇域的成员节点个数Num_i进行比较，确定小簇域及其个数C_Num_change。比较小簇域中 的每个成员节点与其他非小簇域质心的距离，找到离它最近的簇域，将其划归到最近一个非 小簇域中，完成小簇域的拆解。小簇域拆解后，会使某些簇域内的成员节点数过多，所以需 要对这些大簇域进行拆分。对剩余簇域按簇内节点个数的大小进行排序，将排序结果中最大 的C_Num_change个簇域定为大簇域，对大簇域内的成员节点均匀地分成两组，并移出一组形成 新的簇域。不断重复该调整策略，直至网络内簇域的分布趋于均匀，实现簇首个数的稳定和 簇域分布最优。簇域均匀策略的具体实现过程为：

输入：最优成员节点个数Num_opt，簇域分布Cluster_i和成员节点数量Num_i(i＝1,2,…,K_opt)， 算法的最大迭代次数NC_max。

第一步：确定小簇域。比较每个簇域的成员节点数Num_i与最优成员节点个数Num_opt的大 小，若Num_i<Num_opt，则为小簇域Cluster_min_i，统计Cluster_min_i的个数C_Num_change。

第二步：拆解小簇域。将Cluster_min_i中的成员节点重新划归到离其最近的非小簇域中。

第三步：确定大簇域。采用冒泡排序法根据各簇域内的成员节点个数对簇域进行排序， 确定排序结果中最大的C_Num_chang个簇域为Cluster_max_i。

第四步：拆分大簇域。均分Cluster_max_i中的成员节点为两组并将第二组移除，形成新 的簇域。

第五步：终止与返回。当算法的迭代次数到达NC_max，则终止算法并输出结果，否则， 返回第一步继续迭代。

输出：新簇域的分布情况Cluster_i’和成员节点数量Num_i’(i＝1,2,…,K_opt)。

2.3簇首的选举

本发明中，基站根据在数据传输阶段收到的各节点状态包中节点剩余能量的信息，确定 各个簇域的簇首节点，每个簇域选择剩余能量最大的节点作为本簇域的簇首。

创建簇域阶段的算法在基站上实现，并在簇间路由选择完成后，由基站将运行结果向全 网广播。聚类算法分簇和簇域均匀策略只在协议运行的首轮和网络内死亡节点个数增加10％ 以上时才运行，簇首的选举则在协议的每一轮都会运行。

3.簇间路由的选择

本发明中的簇首与基站之间的最优路由选择由蚁群算法实现。

假定蚂蚁数量为m，d_ij(i≠j,j＝0,1,2,…,n)为节点i与j之间的距离，在t时刻蚂蚁各自选 择下一个节点。根据各条路径上的信息素量，蚂蚁在节点i选择节点j的转移概率为:

to_visit＝N-Tabu_k(8)

其中，N表示节点集合，Tabu_k表示第k只蚁群已经过的节点集合即禁忌表，to_visit为待 访问的节点集合即候选集；τ_ij(t)表示t时刻路径ij上的信息素量；η_ij为路径ij的启发因子，我 们取节点i与j之间距离的倒数，如公式(9)所示；α、β分别表示每条路径上信息素和启发因 子的相对重要程度。

${\eta }_{ij}\left(t\right)=\frac{1}{D(i,j)}=\frac{1}{\sqrt{{(x_j-x_i)}^2+{(y_j-y_i)}^2}}---\left(9\right)$

当所有蚂蚁完成一次遍历后，每条路径上的信息素量将根据公式(10)进行更新。

τ_ij(t+1)＝(1-ρ)τ_ij(t)+Δτ_ij(10)

${\mathrm{\Delta \tau }}_{ij}=\underset{k=1}{\overset{n}{\Sigma }}{\mathrm{\Delta \tau }}_{ij}^k---\left(11\right)$

其中，ρ为常数(0<ρ<1)，表示路径上信息素的挥发系数，Δτ_ij表示本次遍历完成后路径 ij上的信息素增量。表示第k只蚂蚁在本次遍历过程中留在路径ij上的信息素。如果蚂蚁 没有经过路径ij，则的值为0。计算公式为：

其中，Q为信息素增强系数，L_k表示第k只蚂蚁在本次遍历过程中经过的路径长度。

具体的实现过程如下：

第一步：参数初始化。设置算法的最大迭代次数为NC_max，初始化每条路径上的信息 素含量、启发因子和其他一些参数。

第二步：簇首发送探测分组。每个簇首将k个探测分组随机地发送至其他簇首，探测分 组每访问一个簇首，自动将该簇首记录到禁忌表Tabu_k中。

第三步：探测分组搜寻基站。每个探测分组依据公式(7)的转移概率发往下一个待访问簇 首，重复运行本步骤，直到探测分组抵达基站。

第四步：信息素的更新。待所有探测分组到达基站后，从每个簇首的探测分组中选出路 径最短的分组，按照公式(12)更新这些探测分组经过的路径上的信息素。至此，完成一次算 法的迭代。

第五步：终止或返回。若算法迭代次数已达到NC_max，则终止蚁群算法并输出最优路 径结果，否则，返回第二步继续迭代。

簇间路由选择阶段的算法也是由基站完成。待基站完成了簇域的建立和簇间路由选择， 会向全网发送广播包。网络中的所有节点接收广播包，并将与自己相关的配置信息存储下来， 在数据传输阶段使用。

4.数据传输

本发明在运行到数据传输的末轮时，采用增加节点状态包的方式，即各节点在发送数据 包的同时增发一个状态包，将节点当前的属性通报给基站。状态包中包含了本节点的剩余能 量、所属簇域、ID号以及位置等信息。通过节点状态包，基站能够完整地掌握网络中所有节 点的实际情况，保证了成簇阶段和簇间路由选择阶段的算法能得出最佳的运行结果。

数据传输阶段的实现过程：首先，各簇域内的簇首采用TDMA方式为成员节点分配发送 数据的时间点，成员节点在其时间点内向簇首发送数据包；然后，簇首整合成员节点的数据， 再发送至基站；簇首在与基站通信过程中会根据其与基站的距离，决定是否采用多跳的方式 向基站发送数据；如果距离大于d₀，则按照蚁群算法得出的最优路由向基站发送数据，否则 簇首直接与基站通信。

5.性能分析

根据无线传感器网络的特点，先对比较协议性能的参量做一些说明。稳定期是指从协议 开始运行到出现第一个节点死亡所经过的时间，不稳定期就是从第一个节点死亡到最后一个 节点死亡的这段时间。网络高效期是指协议从开始运行到超过一半的节点死亡所经过的时间。 传感器网络在网络高效期内能够保持较好的监测性能，当传感器节点死亡数超过一半时，监 测性能就会大幅下降。网络有效期是指网络协议从开始运行到节点死亡率达到90％所经过的 时间。当传感器网络中节点死亡率超过90％时，基本可以判定网络失效。

如图2和图3所示，本发明在运行过程中簇域分布均匀，簇间的路由选择合理，能较好 地减少节点向基站传输数据过程中的能量消耗。

图4和表1是四种协议的网络生存性能的对比。表1描述了本发明所述的KCAOR协议 与LEDACH、SEP和DEEC协议的网络性能的对比：

表1：

在无线传感器网络中，基站需要通过传感器网络获取监测区域的可靠和全面的数据，因 此稳定期的长度是无线传感器网络最重要的度量标准。当网络中节点死亡率在50％以内时， 传感器网络对监测区域能保持较好的数据采集效果；而当节点死亡率超过90％时，网络已经 无法向基站提供监测区域的可靠和全面的数据了，可以判定网络死亡。从对比结果中可以看 到，本发明的稳定期、高效期和有效期的持续时间均好于其他协议，较好地延长了传感器网 络的生存时间。

图5是四种协议能量消耗的对比。从图中可以看到，DEEC协议的能量消耗要低于LEACH 和SEP协议。与DEEC协议相比，KCAOR协议在第400轮、第800轮和第1600轮时的能量 消耗分别减少了29.9％、8.1％和0.5％。这是由于本发明的簇域分布更均匀，簇首数量稳定且 选取合理，较好地降低和均衡了簇内成员节点的能量消耗；簇间采用了最佳的传输路线，进 一步降低了簇首节点的能量消耗，提高了网络能量的使用效率。

图6是四种协议的基站在网络有效期内收到的数据包总数的对比。从图中可以看到，本 发明的基站收到的数据包总数远高于其他协议。数据包总数越大说明网络对监测区域的数据 采集越全面，基站对监测区域的监测能力越好。