基于OWA多属性决策无线传感网分簇算法

代祖浩，陈俊强，代 阳

（1.武汉邮电科学研究院湖北武汉430074；2.东华理工大学测绘工程学院，江西南昌330013）

无线传感器网络（Wireless Sensor Networks，WSN）是一种分布式传感网络，主要作用是通过部署在环境中的节点感知并传递监测到的环境信息。由于监测点空间位置、能量限制、体积等众多因素的影响，WSN中各个节点之间采用无线通信方式传递信息，通过不同的协议栈可以组建出不同类型的多跳自组织网络，其网络配置灵活，支持传感节点位置移动，还可以通过网关或者IP化的无线传感网络协议栈接入互联网[1]，满足信息时代的远程化、智能化的监测控制需求。无线传感网络的核心任务是对环境信息的采集、处理和传输，其与通讯技术和计算机技术一起组成了信息时代的三大支柱。由于无线传感网络节点部署后无法再获得新的能源供给，因此如何减少能源消耗提升网络寿命开始作为WSN研究的主要方向[2-4]。

文献[5]提出的LEACH（LowEnergy Adaptive Clustering Hierarchy，基于低能量自适应簇结构算法）是经典的簇结构算法，但在选举簇头时并没有兼顾节点的余下的能源信息。文献[6]提出EDACH（EnergyDriven Adaptive Clustering Hierarchy）采用代理节点策略。文献[7]提出的EECH（Energy Efficient Clustering Hierarehy）算法，能量越高的节点被选举为簇头的几率越高。文献[8]提出的EECHS算法在LEACH算法的基础上，兼顾了节点的余下能量、距离信息来选择簇头（ClusterHeader，CH）。文献[9]提出的分簇PTTC（Prim based TreeTopology Clustering algorithm for Wireless Sensor）算法兼顾了节点的所剩能量、被选举为簇头的概率选举簇头。但这些算法在路径权值计算方面没有考虑传感设备所剩能源以及路径传输所损耗的能量[10]。

文中探索了一种以PTTC算法为基础改进优化措施。簇头数量和簇头选择依照PTTC算法，但是在计算所传感器节点的权值和路径权值的时候综合考虑节点的剩余能量、是否簇头、路径发送接收损耗。根据计算所得权值利用prim算法[11]建立最优化簇树结构并定时更新保持簇树结构最优化。仿真结果表明，相较于PTTC算法改进后的算法能够更加高效的使网络能量消耗均摊在每个节点上，使得网络能运行的更久的时间[12]。

1 相关工作

多属性决策是指当结果由多种影响因素决定的条件下，确定最优解决策略或排列出各类解决方案[13]。具体思路是采集数据，排列方案，遴选最优。知名学者Yager[14]发表的有序加权平均算子（Ordered Weighted Average operator，OWA）思想，把影响因素对结果影响程序大小排序，依照影响程度赋予不同的权值后将各种因素进行加权汇总，以获得更客观准确的结果评判。本文利用OWA算子集中处理影响路径权值的各种因素，减少主观臆测带来的不良影响，采用熵值最大化作为最终评判标准。

2 系统模型

2.1 算法描述

根据PTTC算法计算出最优的簇头CH个数以及每个传感节点成为簇头CH的概率后，开始分簇网络拓扑结构生成阶段。网络上电启动以后，基站向单跳路径范围内的节点广播探测消息确定其和邻居节点之间的单跳路径权值，收到正确的回复以后更新其路径权值路由表。收到探测消息的节点继续给周围除了发来探测消息来源方以外的其他邻居节点发送探测消息，同样的收到正确回复以后更新其路径权值路由表。遍历完所有节点以后利用Prim算法构建簇树，这样将形成一个初步的、传输路径最优化网络结构。

在该算法中，信息传递路径的规划都考虑了节点余下能源、途经的节点数、路径上的能源消耗等因素。使得网内节点的能源消耗更加平均，同时保持了信息传递路径一直处于最优化状态，从而提高了网络的存活寿命。

2.2 最优簇头数

PTTC算法首先采用了多径衰落的信道模型建立了节点之间无线通讯的能量消耗模型，根据簇头需要融合的数据得出网络运行一轮簇头耗费的能源表示公式。随后根据节点到簇头的距离和所要传输的信息大小推导每个子节点的能源消耗的表达式，进而得出簇内总体能量消耗和簇头个数的关系表达式。最后将总体能量消耗的表达式对簇头个数求导计算出最优的簇头个数mbest：

其中k=λH=λ(4h4)是节点个数，H是传感监测区域的面积，，Enode为节点在收发信息时的能量消耗，εfa为多径衰落的放大器因子，εra为自由空间放大器因子。

以此为基础推导出节点担任簇头的概率pclu：

2.3 节点和路径权值

系统启动后基站开始向周边广播发送网络参数信息，其中包括编号ID、所剩能源node()i.Er、自身参数status。节点将接收到的来自于邻居的广播信息存储在邻居信息表中，统计出邻居节点总数。结合邻居表中记录的参数，综合考虑多个因素的影响程度利用OWA算子确定各类影响因素的比重。最终计算出该节点的权值。用公式表达如下：

公式（1）里：F1是节点单跳范围内其他节点总数；F2是所剩能源参数；F3是传感器距离基站的参数；v1、v2、v3表示上述因素的影响程度比重值的大小。对上述3个关键的影响因素使用下述公式进行归一化运算：

式中：spot(m)∙neinum为网络节点i的单跳路径内的节点数；Nmax∙neighbor为网络节点拥有最多邻居的数量值；Nmin∙neighbor为网络节点拥有最少邻居的数量值；spot(m)∙Pw为网络节点m所余下的能源参数；spot(m)∙Pmax为网络节点m启动前最大可用能量参数；spot(m)∙lentoCS为网络节点m离基站的间距长度；Lmax∙toCS为离基站最远节点到基站的距离；Lmin∙toCS为离基站最近节点到基站的距离。

通过基于最大熵[15]的OWA的决策方法确定各个属性的权重集合{v1，v2，v3} 的权重系数，并且将OWA算子中乐观参数α设置成α=1/2。从而消除了决策者的凭空臆断对结果选择造成的不合理评判，同时将各类影响因素执行归一化计算表示之后能更准确的反映各类影响因素对簇头选择影响程度的权值[16]。

PPTC算法在确定路径权值时只将跳数作为路径权值来衡量路径的优劣，并没有考虑到信息在路径上传递时总共的能源消耗，同时即使是同一条路径随着路径上节点剩余能量的不同，该路径的权值也将随之变化。所以为了使所有节点的能源消耗尽可能的均衡，需要周期性地寻找最佳路径，定义路径权值评估函数如下：

其中:v·spot(m)为接收路径探测消息的节点m的权重参数；v·spot(n)为发送路径探测消息的节点n的权重参数；spot(m)·consum(n)为发送方节点n到接收方节点m的路径消耗的能源。该算法考虑到了路径权值的关键因素：所剩能源、信息传递跳数、周围邻居数量、信息从起点到终点的能源消耗。

2.4 MST的构建

在确定了最优化的簇头数量并选定了担任簇头的节点以后，开始簇树结构的生成阶段。使用Prim算法构建一个最小生成树（Minimum Spanning Tree，MST）网络的过程如图1所示。构建最小生成树网络的目的是为了保证网络内任意节点之间能够通信的前提下使得网络整体开销最小化。

①设定初始状态所有节点聚集在H中。从H中任意一点s出发并将点s放入集合K中。

图1 基于prim算法构建MST的过程

②在H-K剩余的节点中寻找一个节点t使其到K集合中的全部点的权值最小。之后将t节点放入集合K中。

③重复步骤②直到所有节点都加入集合K中。至此即可生成一个最小生成树MST。如果H中包含M个节点，相应的将生成M-1条边[17]。

所有簇头的最小生成树网络生成以后整体的簇树网络结构如图2所示。在网络运行阶段，位于最末梢的传感节点将采集到的信息传递给其上一级节点也就是其父节点，上一级节点随后将信息传递给自己的上一级节点也就是父父节点，数据通过单向流动最终汇聚到了簇树网络的根节点也就是簇头节点处执行数据融合处理。采用Prim算法生成整体网络拓扑结构时，每一个簇头都会形成一个最小生成树网络并担任该MST最终的数据汇聚点进行数据融合处理，以实现各簇头网络之间以及簇头网络和基站之间的信息交换。

图2 完整簇树网络结构

3 算法性能分析

3.1 初始条件

在MATLAB环境进行仿真。仿真参数与PPTC算法保持一致。将节点随机抛洒在100 m*100 m的领域中，基站部署在领域的中央。仿真初设参数设置如表1所示。

表1 仿真初设参数

在该相同的初始条件下选择LEACH、PTTC算法与改进PTTC算法进行重复50次的同步仿真并计算平均值，单次运行时间500 s。并记录对比结果。

3.2 能耗分析

3个算法的运转轮数与能耗记录如表2所示。从表2知在能耗50%时，LEACH、PTTC、改进PTTC分别运行了478轮、1 080轮、1 368轮。从运行相同的轮数来对比能量消耗，可以看出在运行到800轮时，LEACH、PTTC、改进PTTC分别消耗了48.67%、22.43%、18.52%的能量，可以看出改进PTTC算法比LEACH算法和PTTC算法能耗降低了30.15%、3.91%。

表2 3种算法运转轮数与能量消耗

3.3 丢包率

图3可知3种算法的丢包率都随时间在上升，但改进的PTTC算法的丢包率一直处于最低。仿真结束前其最高丢包率为0.12%，说明本改进能保证良好的通讯质量。LEACH算法丢包率最高，也从侧面反映了随机选择簇头会让部分簇头负载不均衡加剧簇头能耗，造成部分簇头早早死亡，导致网络结构断裂，因而产生大量的丢包现象。

图3 3种算法丢包率

4 结 论

针对PTTC算法中信息传递路径固化，节点能源消耗不均衡等问题，设计了完善优化算法。利用OWA算子集中处理所剩能源、两点间通信能耗、节点自身权值等影响路径权值的各种因素，以熵值最大化作为权值评判。该算法能长期保持节点数据传输的最优路径。仿真结果显示改进算法能更均衡网络的能源消耗，使网络运行更长时间。

[1]李凤国.基于6LoWPAN的无线传感器网络研究与实现[D].南京:南京邮电大学，2013.

[2]覃俊翔，许小丰，易可夫，等.采用权函数计时的无线传感器网络分簇算法，计算机工程与应用，2017（3）：138-143.

[3]张华南，李石君，金红.无线传感器网络分簇路由节能研究[J].计算机工程与科学，2015，37（10）:1869-1876.

[4]姜参，王大伟.无线传感网中一种能量均衡的分簇路由算法[J].计算机技术与发展，2014（1）:113-117.

[5] Heinzelmanwr，Chandrakasana，Balakrishnanh．Energy- efficientcommunication protocol for wirelessmicro-sensor networks[C].In Proc.HICSS，2000：1-10．

[6]Kimkt，Younghy．Energy driven adaptive clustering hierarchy（EDACH）for wireless sensor networks[J].LNCS，2005，38（23）：1098-1107．

[7]Huy，Liw，Kangz．Study on energy efficient hierar chical routing protocols of wireless sensor network[C]．InProc．ICIE．2009：325-328．

[8]Raya，Ded.Energy efficient clustering hierarchy protocolfor wireless sensor network[C].in Proc．ICCIA．201l：1-4．

[9]王智超.PTTC:无线传感网络分簇算法[J].电子技术应用，2016（9）:91-94.

[10]石为人，柏荡，高鹏，等.无线传感器网络簇头半径自适应调节路由算法[J].仪器仪表学报，2012，33（8）:1779-1785.

[11]潘大志，陈友军.Prim算法的一种优化实现[J].西华师范大学学报：自然科学版，2011，32（1）:63-66.

[12]柳义筠.一种节能的无线Mesh网络分簇路由协议[J].计算机与现代化，2012（6）:109-112.

[13]张小芝，朱传喜，朱丽.一种基于变权的动态多属性决策方法[J].控制与决策，2014（3）:494-498.

[14]Yager.WeightedmaximumentropyOWAaggregation with applications to decision making under risk[J].IEEE Transactions on Systems， Man， and Cybernetics-Part A:Systems and Humans，2009，39（3）:183-189．

[15]Yager R R．“Centered OWA operators”Soft Comput[J].soft Computing，2007，11（7）:631-639.

[16]王晓晓，冯岩，等.基于Q学习的无线传感网分簇拓扑控制算法[J].郑州大学学报：工学版，2015，36（2）:85-88.

[17]程媛媛.基于Prim最小生成树算法的时间成本研究[J].河北北方学院学报：自然科学版，2013（6）:24-28.