考虑节点能量消耗的无线传感网络平衡路由算法设计

刘运节,包萍

(宁夏师范学院数学与计算机科学学院，固原 756000)

无线传感器网络是由大量传感、数据收集以及低成本的传感器节点构成。在无线传感器网络中，节点的能量受到限制[1-2]。在大规模的网线传感网络中，节点的位置将不停发生变化，方便网络节点随时更新数据的发送方向[3]。但是，如果大量数据突然更新，将会增大网络负担消耗大量能耗。因此，延长整个网络的生命周期成了当前热议的重要内容。

到目前为止，国内学者在平衡路由算法方面已经研究出很多成果，例如，文献[4]提出一种无线传感器网络分簇路由算法，该算法考虑邻近簇首和邻近节点的状态,分级处理,根据簇首位置和簇群范围对簇首进行再优化,通过节点剩余能量、节点间距离和邻近节点,采用中继方式均衡节点能耗,降低网络总能耗，但是降低能耗的效果不佳。文献[5]提出一种高效均衡的路由算法。根据路由网络拓扑结构求取拓扑图边权值，考虑节点能耗的各种影响因素，在此基础上，构建复合权值有向图，并计算最小代价的路径，实现全网能耗均衡。实验结果表明，该方法有效减少了节点能耗，但是能耗开销成本较大。文献[6]提出一种新的路由算法——Beeline路由算法，将数据源的起点与终点作为指导方向，计算当前路由节点到其直线的距离，得到直线最近的路由节点，通过路由跳数以及相邻近路由节点的拥堵状况选择最佳传输。实验结果表明，该方法消耗能耗较少，但是所用成本较高。

由此，现提出考虑节点能量消耗的无线传感网络平衡路由算法。分析不同无线传感网络模块节点的能耗，构建节点的能耗模型，并依据节点能耗模型构建无线传感网络的整体能耗模型，利用蚁群算法求解整体能耗模型，实现无线传感网络平衡路由算法的设计。

1 构建无线传感网络的整体能耗模型

1.1 构建节点总能耗模型

将无线传感器的拓扑抽象为一个全有向图G(V,E)，网络节点集合为V=(v1,v2,…,vn)，邻近加点间的单跳链路集合为E=(e12,e23,…,eij)，其权值代表路径开销weight(vi,vj)，源节点用s(s∈V)表示，用d表示目标节点[7]。得到无线传感器节点目标约束函数为

(1)

如果P=(vs,v1,v2,…,vd)代表从源节点s到目标节点d的路径，则路径参数表示为

(2)

式(2)中：D(P)为路径延时的剩余能量值；cos[t(P)]为路径开销的能量值；E(P)为路径P中最小能量节点的剩余流量值。

每条路径的剩余能量是由该条路径的最小节点决定[8]，因此，取每条路径中最小的节点能量为评价该条路径剩余能量情况的标准。

能量均衡主要是在约束条件下能够找到一条cos[t(P)]较小、E(P)较大的并且满足E(P)≥Emin的路径。如果Dmax是网络允许延时的最大值，Emin为节点允许的最小剩余能量。为了能够更好地说明全局网络剩余情况，需要设定一个比值，即

(3)

式(3)中：E(P)为节点剩余能量值；Eave为节点剩余能量的平均值。

为了维持无线传感网络的稳定性，改进网络存在的问题，在固定时间内，将网络进行更新，并且重新组网[9]。在一个网络周期内，对节点总能耗进行建模，表示为

W=W1+W2

(4)

ET=(Eelec+μrn)b

(5)

ER=Eelecb

W2=cos[t(P)]s-E(P)

(6)

式中：ET为发送能耗；ER为接受能耗；b为固定时间内产生的信息量；r为发送距离；Eelec为射频能耗系数；μ文传感器能耗系数；n为路径损耗指数。

1.2 基于蚁群算法的无线传感网络平衡路由算法

蚁群算法的无线传感网络平衡路由算法具有一定的优势，借助节电能力，促使无线传感网络平衡路由算法相对简单，借助蚁群在较少时间内寻找出新的路径[10]，在利用动态拓扑模型结构，使其路由在实际的应用过程中有着较好的适用性[11]。

在无线传感网络中对多路径路由进行支持的过程中，传感器上的每个节点都会与相邻节点之间链路信息素进行记录，在网络数据进行传输的过程中，根据自身的求解能力，对下一阶段的概率进行选择[12]。当路由出现信息更新时，只需要对传感器相邻节点进行通知就可以，尽可能将每个节点的能量消耗降为最低。

在无线传感网络低能耗路由优化过程中，主要以传感器各节点之间的报文设计、最短路径查找，数据传输和路由维护进行优化处理。

1.2.1 各节点路径选取的可行性分析

无线传感网络各节点报文设计的过程中，蚂蚁包的作用是当sink节点对某一特定的区域进行查询时，要对整个无线传感网络发送消息，并对整个网络各个节点之间的信息素进行重新更新。能量包的作用是在无线传感网络中，任何一个节点能量低于规定好的能量值时，就会将这个信息发给附近节点，使两个节点之间信息素重新更新工作[13]。

在节点信息素重新更新的过程中，计算得到各节点报文分布的相似度SC为

(7)

式(7)中:N(G1)和N(G2)分别为无线传感网络更新过程中组网阶段和通信阶段的索引节点数目；N(G1∩G2)为公共节点数目。

索引通道的连接度表示为

(8)

式(8)中：N(GC)为处理时期的索引节点数目；NGC(G1)为组网中处理阶段的索引节点数目；NGC(G2)为通信阶段中处理时间的索引节点数目。确定索引通道的连接度后，可以依据索引通道连接度确定最短路径，确保选取路径的可行性。

1.2.2 对最短路径查找

在蚂蚁对最短路径查找过程中，也可以看作是无线传感器节点sink在对网络源节点s数据进行查询的过程，将从传感器节点sink向着蚂蚁路径Ap进行移动，一旦出现目的节点sink时，为最短路径[14-15]。

基于误差变换，得到从传感器节点sink向着蚂蚁Ap路径进行移动蚁群的误差函数为

(9)

式(9)中：q为输入无线传感网络的样本数；εk为无线传感器网络中蚁群代表的路由节点路径全局敏感系数；k为路径移动的第k时刻。在D维空间中进行路由均衡设计，根据蚁群的移动速度vi=(vi1,vi2,…,vid)T和蚁群移动过程中的实时位置Xi=(xi1,xi2,…,xid)T，则第i个由蚁群代表的不同无线传感节点位置分布向量Vi=(Vi1,Vi2,…,Vid)，为避免陷入局部最优，对可能出现的误差进行自适应修正，得到各节点分布位置更新为

(10)

(11)

式(11)中：zk为第k节点的速度；xk为第k节点的位置。对每一代蚁群，计算无线传感网络中节点分布的多样性因子f，利用多样性因子寻找最优路径，判断是否达到终止条件，若达到则记录全局最优解，更新种群体，根据多个局部极小点得到第d维(1≤d≤D)蚁群的初始隶属度矩阵，将Xb位置的第i维值替换为Xeb的第i维值，用非线性的方式来调整惯性权重，根据如下方程得到当前全局最优的蚁群位置，即

Vosf=wVid+c1(pid-xid)+c2(pgd-xid)

(12)

xid=xid+wVid

(13)

式中：w为惯性权重；Vid为第i个由蚁群代表的不同无线传感d节点位置分布向量。得到无线传感网络中各个节点的矢量信息为

位置矢量：Xi={xi,1,xi,2,…，xi,D}；

速度矢量：Vi={vi,1,vi,2,…，vi,D}；

个体最优位置矢量：pi={pi,1,pi,2,…，pi,D}。

采用改进的蚁群算法，进行最优节点路径的选取与设计，初始化节点选取的聚类中心，公式为

ea=(Wβ-Wα)/G

(14)

ω=α(I-iV)ea

(15)

式中：Wα、Wβ为节点搜索阈值的上下限；G为选代次数之和；α为聚类系数；I为选取路径的信息素浓度。设定无线传感网络索引的目标函数变量为Q，以整体适应度方差最小为约束条件，对于每个目标函数变量解Xi对应的一个函数为

li(k)=(1-ρ)li(k-1)+γf[xi(k)]

(16)

式(16)中：f[xi(k)]为xi全局最优值；ρ为k时刻第i个蚂蚁向其邻居集合中第j个蚂蚁移动的概率；γ为路径上信息素的系数。蚁群根据个体最优和全局最优来更新自己的速度和位置，利用蚁群算法全局寻优能力强的优点，获取均匀分布节点的全局最优路径Xeb，在迭代搜索过程中，第i个蚂蚁在k+1时刻的位置为

(17)

考虑全局优化问题，得到无线传感网络中节点蚁群的惯性权重[17]，得到索引的准确概率为

(18)

式(18)中：xij(k)为k时刻第i个蚂蚁向其邻居集合中第j个蚂蚁移动的位置；lj(k)为每个目标函数变量解Xj对应的一个函数。此时资源索引的蚂蚁i在d维空间中的位置可以表示为Xi=(xi1,xi2,…，xid)，根据个体最优位置得到第i个蚂蚁准确索集群资源的概率记为Pi=(pi1,pi2,…，pid)，更新后的网络梯度[18]为

(19)

无线传感网络数据传输和低能耗路由维护优化的过程中，在网络数据进行传输时，主要根据各节点信息素和下一阶段的节点进行选择，利用网络数据包对下一阶段节点概率进行计算，使无线网络中各个源节点慢慢的向传感器节点sink移动，在网络数据进行传输时，依据路径将蚂蚁爬行过的节点进行信息素增强，以实现网络数据的维护和最优路径的自动选择。

使用蚁群算法，实现无线传感网络路由优化，在对网络梯度进行更新，获取最短路径上的信息素，以此信息素为基础，将无线传感器节点的信息传向整个网络。

2 实验结果与分析

为了证明所提基于蚁群优化算法的节点非均匀分布无线传感网络的低能耗路由方法的有效性，需要进行实验。实验环境为：Intel Corei3-3220CPU@3.30 GHz,8 GB内存,1.5 TB硬盘容量，该实验为仿真实验。

为了验证所提基于蚁群优化算法的节点非均匀分布无线传感网络的低能耗路由方法的优越性，将所提方法与文献[5]方法以及文献[6]方法节点能耗开销进行对比，对比结果如表1所示。

表1 不同方法的节点能耗开销对比结果Table 1 Comparison of node energy consumption costs of different methods

分析表1可知，节点的能耗开销随着节点数量的增加而增加。当节点的数量为100个时，所提方法的能耗开销为250元，文献[5]方法的能耗开销为350元，文献[6]的能耗开销为290元。当节点数量为400个时，所提方法的能耗开销为350元，文献[5]方法的能耗开销为520元，文献[6]的能耗开销为560元。当节点数量为600个时，所提方法的能耗开销为400元，文献[5]方法的能耗开销为720元，文献[6]的能耗开销为740元。相比3组数据可知，所提方法明显低于其他两种方法。将3种方法的平均节点能耗开销成本进行对比，所提方法的开销成本为320元，文献[6]方法的开销成本为510元，文献[7]方法的开销成本为500元，所提方法分别低于其他两种方法190元、180元。综上可知，所提方法有效降低了能耗开销，节省了成本。

将所提出方法与文献[5]方法以及文献[6]方法进行无线传感网络节点平均能耗(1 e=1.6×10-19C)对比实验，实验结果如图1所示。

由图1可知，3种方法随着迭代次数不断增加，无线传感网络节点平均能耗也随之增加，当迭代次数为100次时，文献[5]方法的节点平均能耗为120 e，文献[6]方法的节点平均能耗为75 e，所提出方法的节点平均能耗为40 e，当迭代次数达到500次时，文献[5]方法的节点平均能耗为140 e，文献[6]方法的节点平均能耗为95 e，所提出方法的节点平均能耗为50 e，文献[5]方法的节点平均能耗与所提出方法相差90 e，文献[6]方法的节点平均能耗与所提出方法相差45 e。实验结果表明，所提出方法的节点平均能耗优于其他2种方法，具有一定应用性能。

图1 不同方法节点平均能耗对比实验Fig.1 Comparison of average energy consumption of different method nodes

测试不同方法在不同迭代次数下的节点分布均匀程度，测试结果如图2所示。

由图2可以看出，在相同条件下，本文方法的节点分布均匀度最高，这是由于本文方法设计无线传感网络路由中，考察了节点的能量消耗以及不同节点能耗的差异性，增加了路由平衡度，从而提高了节点分布均匀度。而文献中的方法随着迭代次数的增加，其节点均匀度并没有固定规律，说明其受到噪声的干扰较大，其节点分布性能不稳定，实际应用性较差。且整体上看，文献中方法始终低于本文方法的节点分布均匀度。该实验结果与无线传感网络能耗测试结果一致，说明节点分布均匀度对无线传感网络的能量消耗具有一定的影响，而本文方法可以有效提高节点分布的均匀度，降低整体无线传感网络的能量消耗。

图2 不同方法的节点分布均匀度对比Fig.2 Comparison of distribution uniformity of nodes in different methods

3 结论

针对传统平衡路由算法存在能耗消耗成本较高、节点消耗能耗过多等问题，提出了一种基于蚁群优化算法的节点非均匀分布无线传感网路的低能耗路由方法。分析不同无线传感网络模块节点的能耗，构建节点的能耗模型，采用改进的蚁群算法，完成无线传感网络路由优化，实现无线传感网络平衡路由的算法设计。实验结果证明，所提方法提高了节点的分布均匀程度，有效降低网络能量消耗，减少能耗开销，为无线传感领域提供有价值的参考。在后续研究中，将针对本文方法的能耗模型进行深入的研究，以期提高运行速度，达到更高的效果，进一步提高本文的方法。