博弈论在无线传感器网络数据转发机制中的应用*

宋 欢，王建娜

（兰州交通大学 电子与信息工程学院，甘肃 兰州 730070）

0 引 言

无线传感器网络（Wireless Sensor Networks，WSN，简称传感器网络）由大量随机分布的低成本微型传感器节点组成，协作地对所观测的区域进行信息采集、数据融合和数据转发，目前已广泛应用于智能交通、医疗救护、环境监测和工业自动化等诸多领域，受到了工业界和学术界的普遍重视[1]。图1为无线传感器网络的具体结构。

网络中的节点（微型传感器）体积小。通过图1可以看出，节点由电池供能，能量非常有限，且当电池能量消耗完时不能进行充电或是更换电池[2]。因此，无线传感器网络的能耗问题成为研究的一个热点。

图1 无线传感器网络构成

无线传感器网络中，数据转发是影响整体能耗的一个关键因素。因为节点能量有限，节点尽可能只发送自身数据，拒绝转发其他节点产生的数据以节省自身能量。这是一种不合作关系，体现了节点的“自私性”。但是，为了保证网络的整体连通性，节点之间必须进行数据转发，才能将信息传送到目的地，这样节点之间又存在一种合作关系，而这种合作称之为联盟。

博弈论是数学领域的一个新型分支，主要研究具有相互依赖行为的参与者决策选择，在现实生活的各大领域有着广泛应用[3]。博弈论是研究在同一种情况下具有竞争关系、存在利益冲突的各个成员为了提高自身的收益而进行的一系列选择的过程。具有这种竞争利益关系的个体称之为参与者，个体成员进行的一系列选择称之为策略。博弈根据成员之间可能存在的关系可以分为合作博弈和非合作博弈。对于非合作博弈，主要是指个体成员尽最大可能去扩大自身收益，同时减少竞争者的收益，强调自身收益。大多数情况下，合作博弈也称为联盟博弈，强调的是参与博弈的个体成员之间有时候为了得到更大的收益，会选择有相同目标的成员进行合作。建立联盟，使联盟的收益尽可能大，强调的是整体收益。本文总结了博弈论在数据转发机制中的拍卖博弈和联盟博弈两种模型。

1 拍卖博弈

不完全信息博弈，是博弈的个体成员之间对彼此的各种信息不完全了解的一种博弈。其中，最常见的是拍卖博弈。拍卖博弈是一种非合作博弈。拍卖也可以理解为买方的竞买，是一个群体进行买卖交易的过程。拍卖的形式各式各样，规则也是千差万别。例如，英式拍卖，拍卖过程有时间限制，在截止时间出价最高的买家可以获得此物，但当出价最高方的价格低于卖方对此物的估价时，卖方可以选择不出售；荷氏拍卖，是将竞拍物品的价格不断降低，直至有人愿意出价为止；暗标拍卖，指的是想参与竞拍的卖方根据自身的情况和对竞标的其他对手进行一个预估给出报价，报价会在一个时间同时公开，出价最高的买方得标，而出价的其他买方不会知道中标的买方的最终收益[4]。除了这些拍卖博弈，还有好多拍卖方式。

文献[5]提出，无线传感器网络的某个节点能量即将耗尽时，将自身的任务信息散布出去，各节点通过协商决定哪个节点继续任务并完成[5]。在数据包转发机制中，由于传感器节点的“自私性”，节点不愿转发来自于其他节点的数据。文献[6]提出了基于拍卖博弈建立了不完全信息的数据转发路径，并提出了对转发节点价格进行博弈进而选择的算法[6]。其实，该算法可以理解为进行的是暗标拍卖。

整个传输路径建立的过程中，为了避免能量较低和建立路径较远的节点当选为下一跳路由，可将剩余能量、节点到Sink节点的跳数作为参考因素。在数据包转发过程中，将发送数据的节点看作拍卖博弈的买方，将该节点的所有邻居节点作为卖方，则卖方节点根据自身的剩余能量以及到Sink节点的跳数给出自己的价格，而买方会根据价格等因素决定下一跳节点。所选的卖方节点会成为新的买方，对下一跳路由节点进行选择。重复该过程，建立一条能耗低、可靠性高的传输路径。博弈过程中，引用了基于奖励机制的博弈模型，即Sink节点会给买方一定的价格作为它数据发送消耗能量的一个补偿，而买方通过拍卖博弈从卖方那里购买需要的服务，一直重复该过程，直到数据到达目标节点。

通过分析可能链路的质量，需对下一跳节点进行一个选择。要考虑节点自身的能量和节点到目标节点的跳数，对链路质量定义如下：

ei(t)表示节点i在t时刻的自身剩余能量；hij表示节点i在t时刻到节点j的跳数。

节点在进行拍卖博弈时如何确定自身收益，文章给出了如下定义，即节点a在时刻t的收益函数：

αa(t)是节点在t时刻数据包转发成功的概率；b是sink节点支付给节点a的价格；esa(t)是节点a在t时刻发送数据所消耗的能量；φ(a, j)是节点a与节点j的交易价格。

在拍卖博弈模型中，节点通过对所有可能的链路的质量和其他等因素的分析，对自身数据进行拍卖。在买方节点中选择下一跳节点，并获得自身收益，选择的下一条买方节点会作为新的卖方节点继续该过程，直至将数据传输至目标节点。拍卖的过程中，充分考虑了节点的剩余能量和跳数，因此可以选择出一条能耗低、可靠性高的路径。

2 联盟博弈

在一个竞争过程中，当参与者较多（参与者大于2）时，为了减少自身消耗，提高自身收益，参与者在进行竞争的同时，有可能选择与有着共同目标的其他参与者合作，使合作的整体获得尽可能大的整体效益。竞争关系结束后，再对整体效益进行分配，从而提高参与者自身的收益[7]，这种关系称之为联盟博弈。即将选择合作的参与者们看成是一个联盟，与其他联盟之间进行竞争。这里建立一个参与者为N人的一个博弈N={n1,n2,n3,…,nn}，v表示效益函数，建立一个联盟U，U∈2N,v(U)则为这个联盟的收益[8]。

联盟博弈的应用有以下两个约束条件：

（1）参与者之间的合作关系建立后，联盟产生的整体效益必须大于参与者单独行动时产生的个人效益之和，即：

（2）在建立的联盟内部，每个参与者最终分配的效益必须大于参与者单独行动时的收益。

联盟内的成员对联盟的整体收益如何进行再分配，常用的几种方式如下。

联盟建立后，没有成员加入或者退出，联盟处于一个稳定的状态。将稳定状态下的联盟叫做具有可传递性（TU）联盟核，描述如下：

联盟内的成员所获得收益不小于成员单独行动时所获得的收益，则有：

θi表示联盟内成员对联盟整体收益分配时的收益。

如果联盟的可传递性核为空或者很大时且无法选择恰当的收益分配集合时，则对于每个联盟成员i∈N，由Shapley值分配的收益为：

对于给定的2个联盟集合U={U1,…,Ul}和S={S1,…,Sp}，定义i▷表示两个联盟的传递的二元关系，iUS▷表示进行联盟博弈的参与者i更偏向于加入联盟集合U。

所以，把稳定集作为联盟博弈的解只适用于某些特殊问题。按联盟成员对联盟贡献的大小进行分配收益具有唯一性和公平性，被广泛应用于各种场景。

在WSN中，数据传输过程是将数据由源节点通过节点转发发送至目标节点。当目标节点相同时，节点为了最大化自身利益，会与其他节点合作，建立一个联盟，最后根据商量好的方案对利益进行再分配。文献[9]将联盟博弈应用到无线传感器网络数据融合过程中，减少了网络的能量消耗，延长了网络的生存周期。联盟建立时，将节点分为源节点和汇聚节点。源节点主要负责数据采集和转发，汇聚节点则是对接收到的数据信息进行融合。如何选择合适的节点建立一个联盟？文献[9]中给出了一个思路，即将数据发送至同一目标汇聚节点且传输路径在一定程度上可以实现的源节点看作一个联盟。在一个联盟中，节点转发数据的数量以及与其他节点合作时所转发数据的数量对联盟的收益有很大影响，同时会消耗节点能量，对消耗的能量可将其视作联盟的成本消耗[9]。

考虑到节点转发数据的数量和节点间合作时转发的数据量的影响，联盟的收益函数定义如下：

pij表示的是联盟内节点发送自身收集的数据数量；qij表示的是联盟内节点转发其他节点的数据的数量。联盟收益函数C其实是联盟内节点的接收数据总量和节点与其他节点之间的合作度的乘积。这里的合作度反映的是联盟内节点与其他节点合作转发的数据数量多少的程度。

关于合作度的描述如下：

式中C代表的是联盟中的源节点，S代表汇聚节点。

假定在t时段源节点ai接收到的数据总量可以定义为：

式中，Ai为节点ai接收的数据流强度；n为接收的数据个数。

在一个联盟中，节点转发数据的数量以及与其他节点合作时转发数据的数量太多，节点消耗能量也会增多。本文中，能耗的模型如下：联盟的特征函数为收益函数除去本身的能量消耗。利用联盟博弈对WSN节点数据融合进行优化，一定程度上降低了节点能耗，延长了网络的生命周期。

3 结 语

通过对博弈论在WSN数据转发机制的研究，本文总结了非合作博弈（拍卖博弈）和合作博弈（联盟博弈）在数据转发、数据融合中的具体应用，理论上一定程度降低了网络能耗，延长了网络的生命周期，但也存在不足。

拍卖博弈模型应用中，在进行链路质量的定义时，考虑到节点到目标节点的跳数，并没有将节点之间的距离考虑在内。如果节点之间跳数少，但是节点之间距离较大，同样会产生较多的能量损耗。

联盟博弈中，能量消耗部分没有考虑到节点自身的电路能耗。在节点之间进行传输时，对自由空间损耗的考虑是否可以忽略，是值得考虑的问题。

现实生活中，博弈论已经应用于各个领域，如金融经济、军事领域、政治领域等。近年，博弈论在无线传感器网络中的应用方面增多，如能耗均衡、定位技术等。博弈论在WSN中的应用虽然存在不足，但对现实生活的意义不可否认。因此，后续将进一步加深对博弈论在WSN中应用的研究。

参考文献：

[1] Lin C,Wu Y,Liu Z,et al.GTCharge:A Game Theoretical Collaborative Charging Scheme for Wireless Rechargeable Sensor Networks[J].Journal of Systems and Software,2016(121):88-104.

[2] 沈士根.基于博弈论的无线传感器网络安全若干关键问题研究[D].上海:东华大学,2013.SHEN Shi-gen.Research on Some Key Issues of Wireless Sensor Network Security Based on Game Theory[D].Shanghai:Donghua University,2013.

[3] 田得润,李长云,张瑶等.博弈论在无线传感器网络路由机制中的应用[J].湖南工业大学学报,2012,26(01):55-60.TIAN De-run,LI Chang-yun,ZHANG Yao,et al.Application of Game Theory in Wireless Sensor Network Routing Mechanism[J].Journal of Hunan University of Technology,2012,26(01):55-60.

[4] 李梦君.暗标拍卖的博弈分析[J].科技创业月刊,2009(09):43-44.LI Meng-jun.Game Analysis of Underbill Auctions[J].Pioneering with Science & Technology,2009(09):43-44.

[5] Li Y,Gao Z,Yang Y,et al.An Improved Auction Scheme for Task Allocation in Wireless Sensor Network[C].Wireless Communications Networking and Mobile Computing(WiCOM),2010:1-4.

[6] 先兴平,刘群,吴涛.拍卖博弈模型在无线传感器网络路由中的应用研究[J].小型微型计算机系统,2012,33(05):1083-1088.XIAN Xing-ping,LIU Qun,WU Tao.Application of Auction Game Model for Wireless Sensor Network Routing[J].Journal of Chinese Computer Systems,2012,33(05):1083-1088.

[7] 吴添英,岳昆,刘惟一.一种无线传感器网络的节能联盟博弈模型[C].中国自动化学会控制理论专业委员会A卷,2011.WU Tian-ying,YUE Kun,LIU Wei-yi.An Energyefficient Coalition Game Model for Wireless Sensor Networks[C].Control Conference (CCC),2011:4940-4945.

[8] Liu Q,Yang S,Zhang L,et al.Game-theory-based Coordination in Wireless Sensor and Actor Networks[J].IET Wireless Sensor Systems,2016,6(05):166-172.

[9] 韩格,杨金华,杨文静等.一种面向无线传感器网络数据融合的路由联盟博弈方法[J].云南大学学报:自然科学版,2011(05):511-516,520.HAN Ge,YANG Jin-hua,YANG Wen-jing,et al.A Routing Coalition Game Approach for Data Fusion in Wireless Sensor Networks[J].Journal of Yunnan University:Natural Science Editi on,2011,33(05):511-516,520.