基于博弈论的WSN有效分簇路由算法的研究

孙艳琴，熊庆国

（武汉科技大学 信息科学与工程学院，湖北 武汉 430081）

无线传感器网络包含了大量无线传感节点。数字电路、无线通信、电池制造技术和微机电系统技术的进步使无线传感器节点变得更小、更廉价、功能更强大且更可靠，同时节点的寿命也逐渐延长。由于在许多情况下无线传感器节点无法从外界获取能量也无法更换电池，因此，无线传感器网络的持续工作能力常依赖于无线传感节点的电池容量。另外，绝大多数无线传感器网络使用多跳通信来避免高能耗、长距离传输。每个传感器节点直接与领域节点通信。因此单个节点能力不足将加重其领域节点的通信负担，从而使部分区域节点的能量很快消尽，最终使整个无线传感器网络失效。

在无线传感器网络中，路由协议[1]起着及其重要的作用，而分簇路由协议更是能均衡网络的能耗，解决无线传感器网络能量受限的问题。分簇路由算法是一种两成架构的传感器网络，其逻辑上可以分为簇内层和簇间层，簇头和其簇内节点构成了簇内层，所有的簇头和sink节点构成了簇间层。簇内层和簇间层按照其路由跳数亦可分为单跳网络和多跳网络。单跳网络（如LEACH等），其簇内节点到簇头、簇头到sink节点均为单跳路由；多跳网络（如LSCP、PEGASIS、ECMR等），其簇内节点到簇头、簇头到sink节点均为多跳路由，则从源节点到目标节点直接可以选择多条路径。图1为分簇多跳网络。

图1 分簇多跳网络Fig.1 Cluster-based multi-hop network

LEACH[2]（Low EnergyAdaptiveClusteringHierarchyProtocol）是第一个基于分簇的路由协议，基本思想是网络中的节点自组组织成簇，在簇结构中，簇首要收集簇内节点采集的数据，同时还要承担路由功能，将簇内节点的冗余数据融合处理后再转发给基站。LEACH随机循环选择簇头结点，将整个网络的能量负载平均分配到每个结点，从而降低网络能量消耗，延长网络生命周期，但是这种随机产生的方式存在以下的缺陷：

1）不能保证簇头节点的均匀分布，不能保证簇的规模的合理性，可能出现的情况是：符点密集的地方簇头节点多，如果产生了多个簇头节点，会产生冗余，造成能量的不合理消耗，从而影响网络寿命；节点稀疏的地方簇头节点少或者没有产生簇头节点，那么部分节点可能没有簇头节点，将造成网络的不完全连通。

2）在LEACH算法中，节点根据自身通信代价最小原则选择加入哪个簇，但是这种方式不能保证簇的负载平衡，因为没有考虑到远离基站较远的簇头能量耗费过快的问题。

针对LEACH算法存在的不足，本文提出一种基于博弈论的有效分簇路由算法 （game efficient clustering routing：GECR）。为了解决路由算法中整体与个体的矛盾，本文在此基础上引入经济学中分析冲突与合作的博弈理论[3]，在簇准备阶段，引入簇首的支付函数A，每一个节点根据支付函数A得出的最佳簇首选择方案，即最佳策略集合；在就绪阶段，簇首根据MTE多跳路由协议[4]与基站通信，避免远离基站的传感器节点能耗过大，从而实现WSN整体能耗均衡。

1 基于博弈论的有效分簇路由算法

1.1 网络模型的构建

无线传感器网络模型[5]基于以下假设：

1）N个传感器节点随机分布在一个m×m的正方形区域内，节点总有数据传送到基站，基站远离监测区域并用于接入到有线网络或者蜂窝无线网络。

2）每个节点具有唯一ID，为了避免网络拓扑结构频繁改变，假定节点部署后不再移动，基站惟一且位置固定。

3）每个节点都具有相同的处理和通信能力，在网络中的地位平等。

4）每个节点都具备数据融合处理功能，节点之间连接对称。

5）每个节点可以根据它与接收者的距离远近，自由调整发射功率以节省能量。

6）网络节点组织成簇结构的形式，簇首执行数据融合处理以减少簇内节点产生的冗余数据，并负责将集中后的数据传输到基站。

1.2 建立节点支付方程

文中综合考虑了节点剩余能量以及邻节点到节点自身的平均路径损耗，将节点i成为簇首的支付函数为

在支付方程中，Ei为节点i的剩余能量，ni为在节点i范围内的邻节点数目，∑Ppathloss表示邻节点到节点i的路径损耗之和，而Einil与PGen分别是节点的初始能量以及节点间传输时的最大传输路径损耗。因此，Ei/Einil表示节点的归一化能量，保证了节点在剩余能量较少的情况下，成为簇首的概率较小；而∑Ppathloss/ni·PGen表示节点周围邻节点到自身的平均路径损耗归一化，该值保证邻节点到备选簇首的平均路径损耗较小的节点，成为最终簇首的概率较大，调节参数a为方程调节因子。

1.3 决策过程

1）利用博弈思想建立网络模型，包括：参与人集合S{s1，s2，…sn}；所有节点在某个时刻的策略所构成的策略集L{l1，l2，…ln}；以及节点i成为簇首时的支付函数A；

2）每一个节点建立邻节点信息集合，并广播A值；

3）接收到邻节点A值的节点，将其与自身A值进行比较，并将大于自身A值的邻节点记录到邻节点信息集中；

4）如果节点的邻节点信息集为空，则自动成为簇首，并广播簇首选择信息；接收到一个或多个簇首选择信息的邻节点，发送归属信息加入A值最大的簇首节点，此时若多个簇首选择信息中的簇首节点具有相同的A值，则随机选择一个作为归属簇并发送归属信息；

5）如果无线传感器节点收到了来自自身邻节点信息集中某个节点发送的归属信息，却没收到任何簇首选择信息，则表明该节点不在任何已生成簇首的传输范围之内，该节点将由邻节点信息集中删去已有归属簇的邻节点，并回到4）；

6）当所有参与人均决定自身策略后，并开始数据传输。

由以上步骤可以看出，在整个过程中，博弈分阶段进行，所有参与人在某一阶段选择策略行动时均知道所有相关参与人在以前阶段所选择的行动；其次所有参与者在选择行动时均是根据所有相关参与人的历史行动策略以及相关信息做出策略选择；再次该多阶段博弈的策略组合在每一个阶段均为纳什均衡；而最终策略组合为完美子博弈均衡。

2 仿真分析

2.1 参数设置

用Matlab[6]生成一个节点分布图，将100个节点随机分布在一个介于（X=0，Y=0）与（X=100，Y=100）的区域内。 sink点置于（50，50）处，其能量可连续供给，如图2所示。在仿真软件中进行参数设置后，分别对网络平均耗能和存活节点的数量进行仿真，结果如图3和图4所示。实验表明，基于博弈论的有效分簇路由算法不但能推迟了节点的死亡时间，而且网络总体平均耗能也相应的减少，无线传感器网络的寿命得到了有效的延长。

图2 在100×100的区域内随机生成100个节点的分布图Fig.2 Map of one hundred node generated randomly in 100×100 region

3 结束语

图3 平均能力消耗变化趋势图Fig.3 Change trends of the average power consumption

图4 存活节点变化趋势图Fig.4 Change trends of the surviving node

文中提出了基于博弈论的有效分簇路由算法（GECR）算法，考虑到节点剩余能量和网络能量均衡两个因素，在簇头节点产生算法和簇的形成这两个方面对传统的LEACH算法进行改进，仿真结果显示，本算法能够有效地使簇首节点合理分布，从而平衡网络负载，节省节点能量，延长网络寿命。

[1]王殊，胡富平，屈晓旭，等.无线传感器网络的理论及应用[M].北京：北京航空航天大学出版社，2007：73-94.

[2]杨玺.面向实时监测的无线传感器网络[M].北京：人民邮电出版社，2010：78-85.

[3]李光久.博弈论基础教程[M].北京：化学工业出版社，2005：31-37.

[3]张盛开，张亚东.现代对策（博弈）论与工程决策方法[M].大连：东北财经大学出版社，2005：86-152.

[4]胡静，沈连丰.基于博弈论的无线传感器网络分簇路由协议[J].东南大学学报，2010，40（3）:441-445.HU Jing，SHEN Lian-feng.Clustering routing protocol of wireless sensor networks based on game theory[J].Journal of Southeast University，2010， 40（3）:441-445.

[5]杨宁，田辉，黄平，等.基于博弈理论的无线传感器网络分布式节能路由算法[J].电子与信息学报，2008，30（5）:1231-1233.YANG Ning，TIAN Hui，HUANG Ping，et al.Distributed energy-economical routing algorithm based on game-theory for WSN[J].Journal of Electronics&Information Technology，2008，30（5）:1231-1233.

[6]马昌凤.最优化方法及其Matlab程序设计[M].北京：科学出版社，2010:60-150.