Ad hoc网络中一种基于转发联盟博弈框架的激励合作路由算法

Ad hoc网络中一种基于转发联盟博弈框架的激励合作路由算法 Incentive Cooperation Routing Algorithm Based on Forwarding Coalitional Game Framework for Ad hoc Networks 1 first-author 王 博，男，高级工程师，博士，现主要从事计算机网络和通信、网络与信息安全方向的研究。E-mail：wbxyz@163.com 王 博，男，高级工程师，博士，现主要从事计算机网络和通信、网络与信息安全方向的研究。E-mail：wbxyz@163.com wbxyz@163.com 1 2 国家计算机网络应急技术处理协调中心，北京 100029 国家计算机网络应急技术处理协调中心，北京 100029 National Computer Network Emergency Response Technical Team/Coordination Center, Beijing 100029, China National Computer Network Emergency Response Technical Team/Coordination Center, Beijing 100029, China 武汉大学 计算机学院，湖北 武汉 430072 武汉大学 计算机学院，湖北 武汉 430072 School of Computer Science, Wuhan University, Wuhan 430072, Hubei, China School of Computer Science, Wuhan University, Wuhan 430072, Hubei, China 为增强Ad hoc网络中节点合作的积极性，借鉴联盟博弈理论，针对节点之间数据包转发过程，定义了转发联盟博弈（forwarding coalitional game，FCG），建立了FCG支付模型，给出了确保形成的大联盟为稳定核的约束条件，并基于经典的按需路由算法对上述模型进行了实现，提出了一种基于FCG框架的激励合作路由（incentive cooperation routing, ICR）算法,并且通过仿真实验对该算法进行了有效性验证。仿真结果表明，该算法在分组投递率、端到端的平均时延、路由开销、联盟支付分配和中间节点转发数据包数量等方面的性能提高显著，能够有效地激励自私节点合作转发的积极性。 In order to enforce the enthusiasm of node cooperation in Ad hoc networks, in this paper, we define the packet forwarding process between nodes as forwarding coalitional game (FCG) based on coalitional game theory, and establish the FCG payment model. We analyze the constraint conditions for the resulting stable core of the grand coalition, implement the above model using the classic on-demand routing algorithm, and propose the incentive cooperation routing (ICR) algorithm based on forwarding coalitional game framework. Furthermore, we verify the effectiveness of this algorithm by simulation experiments. Simulation results show that the performance of the proposed algorithm is improved significantly in term of packet delivery fraction, average end-to-end delay, routing overhead, coalitional payoff allocation and the number of packets forwarded by intermediate nodes, and it also can stimulate the cooperative forwarding initiative of selfish nodes. 联盟博弈 支付分配 稳定核 激励合作 路由算法 coalitional game payoff allocation stable core incentive cooperation routing algorithm 王博,王丽宏,黄传河.Ad hoc网络中一种基于转发联盟博弈框架的激励合作路由算法[J].武汉大学学报（理学版）,2019,65(6):527-537. DOI:10.14188/j.1671-8836.2019.06.001. 0　 引 言 1 Ad hoc网络由许多可以自由移动的节点组成，每个节点扮演主机和路由器双重角色，节点之间的通信通过无线信道、中继节点的多跳转发完成。该网络不依赖于任何固定的基础设施，是无中心控制、完全自组织的，因此它与传统的无线网络有着很大的区别。在传统的紧急情况和军事应用中，Ad hoc网络中的节点都是以一种自愿、积极合作转发的方式工作。但是，在民用领域中，节点自身受到计算、存储和能量等资源的限制，往往会表现出非合作的自私行为 [ 1 1 , 2 2 ] ，以节省自身有限资源的开销，从而影响网络正常的通信性能。因此，确保网络中节点间呈现积极合作的状态及提升网络的性能成为当前Ad hoc网络中研究的热点之一。 当前学术界普遍采用博弈论思想研究Ad hoc网络中的节点激励合作问题 [ 3 3 , 4 4 , 5 5 , 6 6 ] 。但是目前的研究都主要集中于非合作博弈 [ 4 4 , 5 5 , 6 6 ] ，其关注的重点在节点行为方面，即理性节点在通信过程中可选择的策略、博弈可能出现的预期收益和节点对应做出的决策等。而在博弈论另外的研究分支——合作博弈中，一般假定节点之间达成一个可实施的共同行动协议,即节点之间可能表现出一种“合作的意向”，并且这种合作意向是内生的。目前通过采用合作博弈思想增强节点合作转发的相关研究进展如下：文献[ 7 7 ]提出在VANET网络中基于联盟博弈理论的激励合作机制，使得每个节点真实合作地执行路由协议是每个节点获得最大预期利益的目标所在，从而解决了在这种非连通网络环境下数据包合作转发激励问题。文献[ 8 8 ]针对DTN网络提出了一种基于联盟博弈模型分析多理性社区的合作策略，最终通过确定稳定联盟结构优化模型的性能。文献[ 9 9 ]考虑在混合无线移动网络(hybrid wireless mobile networks)中解决移动节点数据包合作转发问题，利用联盟博弈模型分析理性节点参与数据包转发的行为，并提出在联盟形成过程中移动节点可以根据自己的获益情况加入或离开一个联盟，从而确保同一联盟内部节点之间转发数据包是合作的、积极的。文献[ 10 10 ]在文献[ 9 9 ]研究的基础上，建立了贝叶斯联盟博弈模型，对联盟形成过程中的节点行为进行分析，最终通过离散马尔科夫链(DTMC)模型和分布式算法寻找纳什稳定联盟结构以及贝叶斯核(Bayesian core)，保证移动节点都愿意加入到大联盟中，以达到激励合作的目的 。文献[ 11 11 ]为解决自私节点不参与数据包转发的问题，提出了一种基于联盟博弈的选择性解码转发(selective decode-and-forward，SDF)合作激励机制，并对形成的联盟属性和稳定性进行了研究和分析。文献[ 12 12 ]详细介绍了合作博弈论中的联盟博弈概念，并将其在通信网络和无线网络中的实际运用情况进行总结分析。文献[ 13 13 ]利用联盟博弈理论思想，提出了联盟形成算法，解决Ad hoc结构化网络中节点的分簇和扩展性问题。文献[ 14 14 ]提出了基于博弈论框架的随机多路径路由算法，使得网络中的节点为了获得最大化的预期收益而选择最优的博弈策略，以避免网络中恶意节点产生的攻击的影响。目前的研究主要集中在非合作博弈，缺少综合运用联盟博弈思想对不同节点的行为进行评估分析和理论证明方面的研究。为应对非合作博弈理论在解决节点激励合作问题中存在的不足，本文在前期文献[ 15 15 , 16 16 , 17 17 ]研究的基础上，基于合作博弈思想，重点借鉴联盟博弈理论来解决网络中节点激励合作问题，进一步探索提高网络性能和增强网络安全的方法。针对节点数据包转发过程，定义了转发联盟博弈（forwarding coalitional game， FCG），建立了FCG支付模型，给出了确保形成的大联盟为稳定核的约束条件，并基于此模型实现了激励合作路由（incentive cooperation routing, ICR）算法。 1　 预备知识 1 经典博弈论可以分为非合作博弈和合作博弈 [ 12 12 , 18 18 ] 。在非合作博弈中，博弈的参与人根据他们可感知的环境和自身利益进行自主决策。参与人收益不仅取决于自己的行为选择，而且还受到其他参与人行为的影响。在非合作博弈中，参与人收益往往依赖于个体行为，关注的重点在于：理性参与人在竞争环境中可选择的策略是什么？博弈可能产生的预期结果是什么？理性参与人会做出什么样的决策？在合作博弈中，假定参与人有一个可实施的共同行动的协议，即合作是内生的。这时强调的重点在于：这些参与人会形成什么样的联盟？在联盟中，如何确定参与人之间权势的大小？如何合理地分配联盟所得的合作收益（或分摊成本）？ 在非合作博弈中，由各参与人之间的均衡而产生的结果是竞争的产物，一般来说，并不令人满意。因此，他们可能表现出一种外生的“合作的意向” [ 18 18 ] ，但这种合作意向没有严格的执行协议。而在合作博弈中，参与人之间已有一个内生的合作协议，这构成了两类博弈的根本区别。为此，参考经典合作博弈论思想 [ 12 12 , 18 18 ] ，给出如下定义： 定义1 （联盟） 设博弈的参与人集合为 N ={1,2,…, n }，则称集合 N 的任何一个子集 S 为一个联盟。在特殊情况下， S = <math id="M1"><mi mathvariant="normal">∅</mi></math> http://notExist.jpg http://notExist.jpg 3.72533321 3.64066648 或 S = N ，将后一种情况称为一个大联盟(the grand coalition)。 定义2 （特征函数） 设 v ( S )是定义在 N 的一切子集（即联盟）上的实值函数，即 <math id="M2"><mi>v</mi><mtext>:</mtext><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mi>n</mi></mrow></msup><mtext>→</mtext><mi mathvariant="double-struck">R</mi></math> http://notExist.jpg http://notExist.jpg 14.90133286 3.13266659 ( <math id="M3"><mi mathvariant="double-struck">R</mi></math> http://notExist.jpg http://notExist.jpg 2.45533323 2.79399991 为实值集合)，其满足： <math id="M4"><mi>v</mi><mtext>(</mtext><mi mathvariant="normal">∅</mi><mtext>)</mtext><mtext>=</mtext><mn mathvariant="normal">0</mn></math> http://notExist.jpg http://notExist.jpg 15.74800014 3.89466667 ， <math id="M5"><mi>v</mi><mtext>(</mtext><mi>N</mi><mtext>)</mtext><mtext>≥</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>N</mi></mrow></munder><mi>v</mi><mtext>(</mtext><mtext>{</mtext><mi>i</mi><mtext>}</mtext><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 31.15733337 6.77333355 ，则称 v ( S )为一个特征函数。该特征函数也表示为FCG形成的联盟所获得的联盟支付。 定义3 （联盟博弈） 给定参与人集合 N 和特征函数 v ，所进行的合作博弈称为联盟博弈（coalitional game，CG），即表示为CG=( N , v )。 从理论上来说，博弈中所有参与人都愿意加入到大联盟中，大联盟中的任何两个参与人之间都是相互合作的。由于每个参与人都是理性的，可以根据自身所获利益的情况，自由地选择加入到不同的联盟中，因此为了达到节点合作的目的，必须保证每个参与人都愿意选择加入到大联盟中。 在联盟博弈理论中，存在一个重要概念——核(core)，其定义如下： 定义4 （核） 在联盟博弈CG=( N , v )中，核 C ( v )为满足以下条件的支付分配向量 x <math id="M6"><mtext>(</mtext><mi mathvariant="bold-italic">x</mi><mtext>∈</mtext><msup><mrow><mi mathvariant="double-struck">R</mi></mrow><mrow><mi mathvariant="bold-italic">n</mi></mrow></msup><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 12.53066635 3.81000018 的集合： <math display="block" id="M7"><mi mathvariant="bold-italic">C</mi><mtext>(</mtext><mi>v</mi><mtext>)</mtext><mtext>=</mtext><mfenced open="{" close="}" separators="|"><mrow><mi mathvariant="bold-italic">x</mi><mtext>∈</mtext><msup><mrow><mi mathvariant="double-struck">R</mi></mrow><mrow><mi>n</mi></mrow></msup><mtext>|</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>N</mi></mrow></munder><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>=</mtext><mi>v</mi><mtext>(</mtext><mi>N</mi><mtext>)</mtext><mtext>;</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>S</mi></mrow></munder><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>≥</mtext><mi>v</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext><mtext>,</mtext><mtext> </mtext><mtext>∀</mtext><mi>S</mi><mtext>⊆</mtext><mi>N</mi></mrow></mfenced></math> http://notExist.jpg http://notExist.jpg 80.77200317 9.22866726 其中， <math id="M8"><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 2.79399991 3.72533321 为参与人 i 所获得的支付分配。 注意：联盟博弈形成的核是一个向量集合，可以为任意大小集合，也可以为空集。为了确保产生的核是一个非空最优核，则须满足如下条件： 定义5 （最优核） 在联盟博弈CG=( N , v )中，最优核 <math id="M9"><msup><mrow><mi mathvariant="bold-italic">C</mi></mrow><mrow><mi mathvariant="normal">o</mi></mrow></msup><mtext>(</mtext><mi>v</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 9.65199947 3.81000018 的形成必须满足如下条件： 1） 个体理性(individual rationality)： <math id="M10"><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>≥</mtext><mi>v</mi><mtext>(</mtext><mtext>{</mtext><mi>i</mi><mtext>}</mtext><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 18.11866570 4.57200003 ，即任何一个参与人加入到联盟博弈CG中，其所获得的支付分配至少应该比其单独形成联盟获得的支付分配高。 2） 联盟理性(coalitional rationality)：由于参与人的理性，其自身可能离开当前所加入的联盟，而选择加入形成的其他联盟中，来使其获得的支付分配最大化。 3） 有效性(effectiveness)： <math id="M11"><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>N</mi></mrow></munder><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>=</mtext><mi>v</mi><mtext>(</mtext><mi>N</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 20.82799911 6.77333355 ，即联盟博弈中所有参与人的支付分配总额与大联盟所获得的联盟支付分配达到平衡，不存在或多或少的情况。 2　 转发联盟博弈支付模型 1 2.1　转发联盟博弈定义 2 为增强Ad hoc网络中节点合作的积极性，本文提出了转发联盟博弈（FCG）支付模型，参照定义3，本节首先给出FCG的定义。 定义6 （FCG） 给定网络中参与数据包转发的节点集合 N 和特征函数 <math id="M12"><mi>v</mi></math> http://notExist.jpg http://notExist.jpg 1.86266661 2.79399991 ，节点之间参与数据包转发的合作博弈过程称为数据包转发联盟博弈（forwarding coalitional game，FCG），即表示为FCG=( N , <math id="M13"><mtext> </mtext><mi>v</mi></math> http://notExist.jpg http://notExist.jpg 2.62466669 2.79399991 )。 为了给出 <math id="M14"><mi>v</mi></math> http://notExist.jpg http://notExist.jpg 1.86266661 2.79399991 的计算公式，现对FCG过程给出如下假设条件： 1) 整个网络 G ( V , E )由 n 个节点构成， G 为任意有向图， V 与 E 则分别表示为 n 个节点构成的节点集合及节点之间链路构成的边集合。 2) 当且仅当节点 x ， y 处于彼此传输范围时，其间链路( x , y ) <math id="M15"><mtext>∈</mtext></math> http://notExist.jpg http://notExist.jpg 2.70933342 3.13266659 E ，且 E 中所有链路均是双向的。 3) 节点在进行正常通信时，都以混杂模式工作，以便监听其周围邻居节点合作转发数据包的情况。 4) 网络中每个节点 i 在参与数据包转发过程中，如该节点对收到的数据包进行转发则称其行为为合作行为；如该节点不接收数据包或不转发数据包则称其行为为自私行为。 5) 在数据包转发联盟博弈（简称为“转发联盟博弈”）FCG=( N , v )中，博弈过程是从源节点src发送数据包开始，到目的节点dest收到源节点发送的数据包为止。其中， N = V 。 6) FCG中的节点都是理性的，节点根据自身收益情况自主决定加入或退出当前的联盟，但是节点都以追求获得收益最大化为目标（即网络中的节点所获得的支付分配都不小于0）。 7) FCG形成的联盟为非重叠联盟，即网络中的任何节点最终只能加入到一个联盟中，并且联盟之间不存在交叉重叠情况。此外，联盟中的任何节点之间是相互合作的。 8) src为了确保完成与dest正常的通信过程，需要给联盟中参与转发数据包的转发节点支付相应的费用，以弥补中间节点接收和转发数据包产生的成本开销。因此，本文为src预先设置最大的支付费用阈值 M src 。 随着转发联盟博弈过程的持续进行，节点之间通过逐步通信交互形成了若干联盟。假设存在一个联盟 S <math id="M16"><mtext>(</mtext><mi>S</mi><mtext>⊆</mtext><mi>N</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 14.05466652 3.55599999 ，根据 S 中所有节点接收和转发数据包的情况， S 的特征函数计算公式如下 <math display="block" id="M17"><mi>v</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext><mtext>=</mtext><mi>δ</mi><mtext>⋅</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>-</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>S</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 73.74466705 7.02733326 其中， <math id="M18"><mi>δ</mi></math> http://notExist.jpg http://notExist.jpg 1.94733334 2.79399991 为从src发送数据包成功到达dest的奖励因子（ <math id="M19"><mn mathvariant="normal">0</mn><mtext><</mtext><mi>δ</mi><mtext>≤</mtext><mn mathvariant="normal">1</mn></math> http://notExist.jpg http://notExist.jpg 16.84866714 3.30199981 ）； C ( i )为联盟中参与转发的节点 i 由于接收和转发数据包而产生的成本； m r ( i )和 m f ( i )分别为联盟中参与转发的节点 i 接收到的数据包个数和实际转发的数据包个数。 具体联盟形成的示意图如 图1 图1 所示。 图1 图1 (a)中11个节点形成了两个联盟：联盟1和联盟2。 图1 图1 (b)中11个节点形成了包含所有节点的大联盟。 2.2　转发联盟成员支付分配定义 2 由于联盟的形成是为了确保将数据包成功发送至目的节点，即在形成的联盟中节点之间是相互合作的，因此本文根据联盟中参与节点的不同通信行为角色类型（参与转发数据包的过渡节点：中间节点;数据包最终到达的结束节点：目的节点; 数据包初始发送的起始节点：源节点）分别定义各自支付分配的计算方法。 1） 中间节点 3 由于联盟中的中间节点是除源节点和目的节点之外而存在的核心节点,在通信过程中，这类节点主要承担通信行为角色：从上一跳邻居节点接收发送的数据包并转发数据包给下一跳邻居节点。因此，在本文中，主要考虑此类节点的接收和转发行为对其支付分配产生的影响。假设中间节点为 i ，其对应的支付分配为 <math display="block" id="M20"><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>=</mtext><mi>α</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><mi>β</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>-</mtext><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 78.31666565 4.82599974 其中， <math id="M21"><mi>α</mi></math> http://notExist.jpg http://notExist.jpg 1.94733334 2.79399991 和 <math id="M22"><mi>β</mi></math> http://notExist.jpg http://notExist.jpg 1.94733334 3.81000018 分别为 i 由于接收和转发数据包而从src获得的支付补偿因子。为了保证节点的理性， <math id="M23"><mi mathvariant="normal">令</mi><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>≥</mtext><mn mathvariant="normal">0</mn></math> http://notExist.jpg http://notExist.jpg 14.39333344 4.48733330 。 2） 目的节点 3 目的节点在联盟中主要承担通信行为角色：仅仅是被动地从上一跳周围邻居节点中接收所要发送的数据包，可以看作是中间节点无转发行为时的特殊情况。假设目的节点dest对应的支付分配为 <math display="block" id="M24"><msub><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">d</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mtext>=</mtext><mi>α</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi mathvariant="normal">d</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi><mtext>)</mtext><mtext>-</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi mathvariant="normal">d</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi mathvariant="normal">d</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 62.39933395 4.48733330 (3)式和 (2) 式类似，即与 (2) 式中 m f (dest)=0的情况等价。其中， <math id="M25"><mi>C</mi><mtext>(</mtext><mi mathvariant="normal">d</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 12.44600010 3.55599999 为dest接收数据包时所产生的成本费用。显然， <math id="M26"><msub><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">d</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mtext>≥</mtext><mn mathvariant="normal">0</mn></math> http://notExist.jpg http://notExist.jpg 13.12333298 4.14866638 。 3） 源节点 3 src为了与dest建立正常的通信联系，在整个联盟中一方面向dest发送数据包，另一方面还要向联盟中的中间节点和dest支付相应的成本开销。因此，根据src设置的最大支付阈值 M src ，定义其对应的支付分配为 <math display="block" id="M27"><msub><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>=</mtext><mi>δ</mi><mtext>⋅</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>-</mtext><mfenced open="[" close="]" separators="|"><mrow><mi>α</mi><mtext>⋅</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><mi>β</mi><mtext>⋅</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext></mrow></mfenced></math> http://notExist.jpg http://notExist.jpg 109.05067444 10.32933331 2.3　实现转发联盟结构稳定性的约束条件 2 FCG中各个节点均通过自主选择加入到大联盟中，实现自身支付分配最大化，即使得大联盟中的节点之间都是相互合作的，不存在自私的非合作行为。因此，本节通过对联盟博弈思想中大联盟的非空最优核特性（包括个体理性、联盟理性和有效性，具体见定义5）进行研究，重点围绕FCG中 N 个节点形成的大联盟具有稳定和非空的联盟结构特性进行分析。本节针对2.2节所提出的节点支付分配定义，参照定义5，给出对应具备3种特性的情况下支付分配应满足的约束条件，具体如下。 1） 个体理性约束条件 3 引理1 在转发联盟博弈FCG=( N , v )中，为了确保 N 中所有节点都满足个体理性，使得(2)、(3)和(4) 式中的支付分配成立，需要FCG满足如下条件 <math display="block" id="M28"><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi><mtext>(</mtext><mi>α</mi><mtext>,</mtext><mi>β</mi><mtext>)</mtext><mtext>≤</mtext><mfrac><mrow><mi>δ</mi><mtext>⋅</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub></mrow><mrow><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub></mrow></mfrac></math> http://notExist.jpg http://notExist.jpg 34.79800034 8.55133343 其中， <math id="M29"><msub><mrow><mi>m</mi></mrow><mrow><mi>r</mi></mrow></msub><mtext>=</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 31.91933250 7.02733326 ， <math id="M30"><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>=</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 31.66533279 7.02733326 。 证 在大联盟形成理论中，证明联盟中所有节点都满足个体理性，即需要证明节点 i 的支付分配满足: <math id="M31"><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>≥</mtext><mi>v</mi><mtext>(</mtext><mtext>{</mtext><mi>i</mi><mtext>}</mtext><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 19.30399895 4.57200003 且 <math id="M32"><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>≥</mtext><mn mathvariant="normal">0</mn></math> http://notExist.jpg http://notExist.jpg 10.49866676 4.14866638 。可以利用2.2节中各个节点的支付分配定义进行证明。 情况1（针对中间节点 i 的支付分配情况）：如中间节点 i 形成一个独立的联盟 <math id="M33"><mtext>{</mtext><mi>i</mi><mtext>}</mtext></math> http://notExist.jpg http://notExist.jpg 4.91066647 3.55599999 ，则 <math id="M34"><mi>v</mi><mtext>(</mtext><mtext>{</mtext><mi>i</mi><mtext>}</mtext><mtext>)</mtext><mtext>=</mtext><mn mathvariant="normal">0</mn></math> http://notExist.jpg http://notExist.jpg 17.27199936 3.55599999 ；同时由于 m r ( i )= m f ( i )=0，则 <math id="M35"><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>=</mtext><mn mathvariant="normal">0</mn></math> http://notExist.jpg http://notExist.jpg 9.73666668 3.72533321 。即 <math id="M36"><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>=</mtext><mi>v</mi><mtext>(</mtext><mtext>{</mtext><mi>i</mi><mtext>}</mtext><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 18.54199982 4.48733330 。 情况2（针对目的节点dest的支付分配情况）：如dest形成一个独立的联盟 <math id="M37"><mtext>{</mtext><mi mathvariant="normal">d</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi><mtext>}</mtext></math> http://notExist.jpg http://notExist.jpg 9.90599918 3.55599999 ，则 v ( <math id="M38"><mtext>{</mtext><mi mathvariant="normal">d</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi><mtext>}</mtext></math> http://notExist.jpg http://notExist.jpg 9.90599918 3.55599999 )=0；同理由于 m r (dest)=0，则 <math id="M39"><msub><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">d</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mtext>=</mtext><mn mathvariant="normal">0</mn></math> http://notExist.jpg http://notExist.jpg 11.42999935 3.72533321 。即 <math id="M40"><msub><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">d</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi></mrow></msub><mtext>=</mtext><mi>v</mi><mtext>(</mtext><mtext>{</mtext><mi mathvariant="normal">d</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi><mtext>}</mtext><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 25.31533432 4.48733330 。 情况3（针对源节点src的支付分配情况）：类似于情况1和情况2，src形成一个独立的联盟 <math id="M41"><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext></math> http://notExist.jpg http://notExist.jpg 8.04333305 3.55599999 ，该联盟对应的支付为 v ( <math id="M42"><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext></math> http://notExist.jpg http://notExist.jpg 8.04333305 3.55599999 )=0。而根据 (4)式，src的支付分配为 <math display="block" id="M43"><mtable columnalign="left"><mtr><mtd><msub><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>=</mtext><mi>δ</mi><mtext>⋅</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>-</mtext><mfenced open="[" close="]" separators="|"><mrow><mi>α</mi><mtext>⋅</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><mi>β</mi><mtext>⋅</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext></mrow></mfenced></mtd></mtr><mtr><mtd><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext>≥</mtext><mi>δ</mi><mtext>⋅</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>-</mtext><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi><mtext>(</mtext><mi>α</mi><mtext>,</mtext><mi>β</mi><mtext>)</mtext><mfenced open="[" close="]" separators="|"><mrow><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><mtext>            </mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext></mrow></mfenced><mtext>=</mtext></mtd></mtr><mtr><mtd><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mi>δ</mi><mtext>⋅</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>-</mtext><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi><mtext>(</mtext><mi>α</mi><mtext>,</mtext><mi>β</mi><mtext>)</mtext><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>)</mtext><mtext> </mtext><mtext>≥</mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mn mathvariant="normal">0</mn></mtd></mtr></mtable></math> http://notExist.jpg http://notExist.jpg 105.66399384 29.20999908 为了满足源节点src的个体理性，需保证 <math id="M44"><msub><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>≥</mtext><mi>v</mi><mtext>(</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 24.12999916 4.57200003 ，由于 v ( <math id="M45"><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext></math> http://notExist.jpg http://notExist.jpg 8.04333305 3.55599999 )=0，因此只需确保 <math id="M46"><msub><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>≥</mtext><mn mathvariant="normal">0</mn></math> http://notExist.jpg http://notExist.jpg 12.19199944 4.14866638 即可。综上，通过计算不等式得出需要满足的前提条件如下 <math display="block" id="M47"><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi><mtext>(</mtext><mi>α</mi><mtext>,</mtext><mi>β</mi><mtext>)</mtext><mtext>≤</mtext><mfrac><mrow><mi>δ</mi><mtext>⋅</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub></mrow><mrow><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub></mrow></mfrac></math> http://notExist.jpg http://notExist.jpg 34.79800034 8.55133343 证毕。 2） 联盟理性约束条件（如不满足此理性要求，联盟结构存在不稳定的可能性） 3 根据文献[ 7 7 , 8 8 , 9 9 , 10 10 ]所述，如果联盟中的节点不满足联盟理性的条件，节点有可能离开大联盟，而加入形成的其他联盟中，来使其支付分配达到最大化。为了便于分析，本文针对(1)式中的奖励因子 <math id="M48"><mi>δ</mi></math> http://notExist.jpg http://notExist.jpg 1.94733334 2.79399991 进行重新定义，即将 <math id="M49"><mi>δ</mi></math> http://notExist.jpg http://notExist.jpg 1.94733334 2.79399991 构造为联盟 S <math id="M50"><mtext>(</mtext><mi>S</mi><mtext>⊆</mtext><mi>N</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 14.05466652 3.55599999 的函数 <math id="M51"><mi>δ</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 7.78933334 3.55599999 。具体定义如下 <math display="block" id="M52"><mi>δ</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext><mtext>=</mtext><mfrac><mrow><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>S</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext></mrow><mrow><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub></mrow></mfrac></math> http://notExist.jpg http://notExist.jpg 51.30799866 11.85333347 在上式中， <math id="M53"><mi>δ</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 7.78933334 3.55599999 即为在联盟 S 中除src之外的所有节点接收和转发数据包的总数与大联盟中除src之外的所有节点接收和转发数据包总数的比值，也可以理解为针对联盟 S 中节点之间相互转发数据包（转发和接收行为）而产生的合作行为所占的比例。很显然，在大联盟中，节点之间都是相互合作的，可以得出： <math id="M54"><mi>δ</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext><mtext>=</mtext><mn mathvariant="normal">1</mn></math> http://notExist.jpg http://notExist.jpg 14.30866623 3.55599999 。本文通过引入 <math id="M55"><mi>δ</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 7.78933334 3.55599999 ，进一步将联盟支付 <math id="M56"><mi>v</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 7.70466709 3.55599999 的计算公式进行替换 <math display="block" id="M57"><mi>v</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext><mtext>=</mtext><mfrac><mrow><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>S</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext></mrow><mrow><mtext>         </mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub></mrow></mfrac><mtext>⋅</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>-</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>S</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 64.76999664 20.65866661 为了联盟结构的稳定，需确保在大联盟中的任何节点均不产生离开大联盟的意愿，即任何节点都自愿加入到大联盟中，确保在大联盟中所获得的支付分配最大。本文通过如下引理证明达到以上要求所需满足的条件。 引理2 在转发联盟博弈FCG=( N , v )中，假设任意联盟 S <math id="M58"><mtext>(</mtext><mi>S</mi><mtext>⊆</mtext><mi>N</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 14.05466652 3.55599999 对应的联盟支付为 <math id="M59"><mi>v</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 7.70466709 3.55599999 （（6）式）， 为了确保 S 满足联盟理性，使得 (2)、(3)和(4)式中的支付分配成立，则需要满足如下条件 <math display="block" id="M60"><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi><mtext>(</mtext><mi>α</mi><mtext>,</mtext><mi>β</mi><mtext>)</mtext><mtext>≤</mtext><mfrac><mrow><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub></mrow><mrow><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub></mrow></mfrac></math> http://notExist.jpg http://notExist.jpg 34.79800034 8.55133343 即确保大联盟中任何理性节点都不会离开大联盟而加入到其他联盟中。 证 情况1： 假如联盟 S 中包括src，一个中间节点 i 和dest，则对联盟 S 的联盟理性证明转化为对个体理性的证明。由引理1可知，此情况下联盟 S 满足联盟理性。 情况2： 假如联盟 S 中包括src和dest节点，并存在若干中间节点。需要对 <math id="M61"><mi>v</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 7.70466709 3.55599999 和大联盟中部分节点在联盟 S 所获得的支付分配之和( <math id="M62"><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>S</mi></mrow></munder><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 7.53533316 6.77333355 )进行对比。显然，如果 <math id="M63"><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>S</mi></mrow></munder><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>≥</mtext><mi>v</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 21.42066574 6.77333355 ，则表示不存在有任何节点集合的子集形成的某一联盟获得的联盟支付比在大联盟中对应获得的支付分配之和大的情况。因此，本文只需要证明 <math id="M64"><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>S</mi></mrow></munder><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>≥</mtext><mi>v</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 21.42066574 6.77333355 即可。具体证明过程如下 <math display="block" id="M65"><mtable columnalign="left"><mtr><mtd><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>S</mi></mrow></munder><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>-</mtext><mi>v</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext><mtext>=</mtext></mtd></mtr><mtr><mtd><msub><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>+</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>S</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>-</mtext><mi>v</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext><mtext>=</mtext></mtd></mtr><mtr><mtd><mi>δ</mi><mtext>⋅</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>-</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><mtext>(</mtext><mi>α</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><mi>β</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext></mtd></mtr><mtr><mtd><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>S</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><mtext>(</mtext><mi>α</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><mi>β</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>-</mtext><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>-</mtext><mi>v</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext><mtext>=</mtext></mtd></mtr><mtr><mtd><mfrac><mrow><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>N</mi></mrow></munder><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext></mrow><mrow><mtext>  </mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub></mrow></mfrac><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>-</mtext></mtd></mtr><mtr><mtd><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>S</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext></mtd></mtr><mtr><mtd><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext>-</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mi>S</mi><mtext>)</mtext></mrow></munder><mtext>(</mtext><mi>α</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><mi>β</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext></mtd></mtr><mtr><mtd><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext>-</mtext><mfrac><mrow><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>S</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext></mrow><mrow><mtext>  </mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub></mrow></mfrac><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>+</mtext></mtd></mtr><mtr><mtd><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>S</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext></mrow></munder><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>≥</mtext></mtd></mtr><mtr><mtd><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>-</mtext><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi><mtext>(</mtext><mi>α</mi><mtext>,</mtext><mi>β</mi><mtext>)</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mi>S</mi><mtext>)</mtext></mrow></munder><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>-</mtext></mtd></mtr><mtr><mtd><mtext>(</mtext><mn mathvariant="normal">1</mn><mtext>-</mtext><mfrac><mrow><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mi>S</mi><mtext>)</mtext></mrow></munder><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext></mrow><mrow><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub></mrow></mfrac><mtext>)</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>≥</mtext></mtd></mtr></mtable></math> http://notExist.jpg http://notExist.jpg 99.90666962 109.05067444 <math display="block" id="M66"><mtable columnalign="left"><mtr><mtd><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mi>S</mi><mtext>)</mtext></mrow></munder><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>⋅</mtext><mtext>(</mtext><mfrac><mrow><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub></mrow><mrow><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub></mrow></mfrac><mtext>-</mtext><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi><mtext>(</mtext><mi>α</mi><mtext>,</mtext><mi>β</mi><mtext>)</mtext><mtext>)</mtext></mtd></mtr><mtr><mtd><mtext>≥</mtext><mtext> </mtext><mtext> </mtext><mn mathvariant="normal">0</mn></mtd></mtr></mtable></math> http://notExist.jpg http://notExist.jpg 75.86133575 13.97000027 因此，为了确保 <math id="M67"><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>S</mi></mrow></munder><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>≥</mtext><mi>v</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 21.42066574 6.77333355 ，只需通过计算不等式得出需要满足的前提条件即可，即： <math display="block" id="M68"><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi><mtext>(</mtext><mi>α</mi><mtext>,</mtext><mi>β</mi><mtext>)</mtext><mtext>≤</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>/</mtext><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 44.53466797 4.99533367 证毕。 3） 有效性约束条件 3 为了确保FCG中大联盟中所有节点的支付分配均具有有效性，只需对所有节点的支付分配总和与该联盟对应的联盟支付进行权衡对比，确保不存在或多或少的情况。假设 N 中任意节点 i 的支付分配为 <math id="M69"><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 2.79399991 3.72533321 ，大联盟的联盟支付为 <math id="M70"><mi>v</mi><mtext>(</mtext><mi>N</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 8.88999939 3.55599999 ，则 N 中所有节点的支付分配之和为 <math id="M71"><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>N</mi></mrow></munder><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 7.70466709 6.77333355 。 引理3 在大联盟中，为了大联盟中所有节点的支付分配具有有效性，需满足如下条件： <math id="M72"><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>N</mi></mrow></munder><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>=</mtext><mi>v</mi><mtext>(</mtext><mi>N</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 21.92866707 6.77333355 。 证 由于大联盟中包含了源节点src和目的节点dest，则 N 中所有节点的支付分配之和为 <math id="M73"><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>N</mi></mrow></munder><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 7.70466709 6.77333355 。根据 (2)、(3)和(4)式，则 <math id="M74"><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>N</mi></mrow></munder><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 7.70466709 6.77333355 计算如下 <math display="block" id="M75"><mtable columnalign="left"><mtr><mtd><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mi>N</mi></mrow></munder><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>=</mtext><msub><mrow><mi>x</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>+</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>=</mtext></mtd></mtr><mtr><mtd><mi>δ</mi><mtext>⋅</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>-</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><mtext>(</mtext><mi>α</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><mi>β</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext></mtd></mtr><mtr><mtd><mtext> </mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><mtext>(</mtext><mi>α</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><mi>β</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext> </mtext><mtext>-</mtext><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>=</mtext></mtd></mtr><mtr><mtd><mi>δ</mi><mtext>⋅</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>-</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>=</mtext></mtd></mtr><mtr><mtd><mi>v</mi><mtext>(</mtext><mi>N</mi><mtext>)</mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext></mtd></mtr></mtable></math> http://notExist.jpg http://notExist.jpg 97.45133209 38.77733231 显然，大联盟所有节点的支付分配具有有效性。证毕。 综上（引理1、2和3）所述，给出如下定理： 定理1 在转发联盟博弈FCG=( N , v )中，假设任意联盟 S <math id="M76"><mtext>(</mtext><mi>S</mi><mtext>⊆</mtext><mi>N</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 14.05466652 3.55599999 对应的联盟支付为 <math id="M77"><mi>v</mi><mtext>(</mtext><mi>S</mi><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 7.70466709 3.55599999 , N 中任意节点 i 的支付分配为 <math id="M78"><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://notExist.jpg http://notExist.jpg 2.79399991 3.72533321 ，如果满足如下两个条件： 条件1： <math id="M79"><mi>α</mi></math> http://notExist.jpg http://notExist.jpg 1.94733334 2.79399991 和 <math id="M80"><mi>β</mi></math> http://notExist.jpg http://notExist.jpg 1.94733334 3.81000018 参数满足 <math display="block" id="M81"><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi><mtext>(</mtext><mi>α</mi><mtext>,</mtext><mi>β</mi><mtext>)</mtext><mtext>≤</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>/</mtext><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>)</mtext></math> http://notExist.jpg http://notExist.jpg 44.36533356 4.99533367 条件2： <math display="block" id="M82"><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><mtext>=</mtext><mfenced open="{" close="" separators="|"><mrow><mtable columnalign="left"><mtr><mtd><mi>α</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><mi>β</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>-</mtext><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext> </mtext><mtext>,</mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mtext> </mtext><mi mathvariant="normal">i</mi><mi mathvariant="normal">f</mi><mtext> </mtext><mtext> </mtext><mtext> </mtext><mi>i</mi><mtext>≠</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mtd></mtr><mtr><mtd><mi>δ</mi><mtext>⋅</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>-</mtext><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>∈</mtext><mtext>(</mtext><mi>N</mi><mtext>-</mtext><mtext>{</mtext><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi><mtext>}</mtext><mtext>)</mtext></mrow></munder><mtext>(</mtext><mi>α</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>+</mtext><mi>β</mi><mtext>⋅</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>)</mtext><mtext>⋅</mtext><mi>C</mi><mtext>(</mtext><mi>i</mi><mtext>)</mtext><mtext>,</mtext><mi mathvariant="normal">o</mi><mi mathvariant="normal">t</mi><mi mathvariant="normal">h</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">w</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">e</mi></mtd></mtr></mtable></mrow></mfenced></math> http://notExist.jpg http://notExist.jpg 80.85666656 12.53066635 则 N 中所有节点的支付分配具有核的特性，并且此时形成的大联盟具有稳定和非空的联盟结构特性。 该定理的证明过程参见上述引理的证明过程。 定理1通过对FCG节点支付分配的定义，一方面，使节点所获得的支付分配最大化；另一方面，使各个节点都愿意加入到大联盟中，即各个节点都积极地参与到数据包的转发过程中，不存在自私的非合作行为，从而确保转发联盟结构的稳定性能够得到有效地收敛，网络节点之间的合作能保持一种稳定的状态。 3　 本文算法 1 本节在Ad hoc网络中的路由算法基础上进行扩展研究，提出了基于上述FCG支付模型的激励合作路由(ICR)算法。ICR算法是在Ad hoc网络中经典的按需路由算法（AODV，DSR和TORA等 [ 1 1 ] ）的基础上进行改进而实现的。该算法除了路由请求建立过程和路由回复应答过程之外，还要在这两个过程中完成网络中各个节点的支付分配，从而使得各个节点都能够获得最大的收益，避免节点产生自私行为。 假定源节点src和目的节点dest需要建立一条合作路由，为了确保所建路由上的中间节点都是合作的，设计了如下实现过程。 3.1　路由请求建立过程 2 该过程主要利用动态源路由建立的思想，完成从src到dest的路由发现过程。src首先查找本地路由表中是否存在到达dest的路由。如存在，则直接发送数据包，完成正常的通信；如不存在，则src将自身发送数据包的消耗成本以〈src, cost〉字段添加到路由请求包REQ的辅助记录中，并继续向下一跳邻居节点广播REQ包 。 中间节点收到发送的REQ包后，通过对比，执行如下步骤：如果该节点已重复收到此路由建立请求，或者该节点已经在该REQ的路由记录中，那么该节点将丢弃该REQ包，等待其他邻居节点发送REQ包。否则，该节点将对该REQ路由记录中的最后一跳节点进行分析，并在该REQ的辅助记录中找到对应节点的消耗成本，并在本地邻居节点信息表LocalNHTable中设置最后一跳节点的相关信息：“发送数据包类型”字段填充为REQ，“接收数据包”字段和“转发数据包”字段填充为Y，“消耗成本”字段填充辅助记录中对应节点的消耗成本情况，同时将该节点的信息附加到REQ包的路由记录中，将该节点因为转发REQ包对应的消耗成本字段添加到REQ的辅助记录中，并将更新后的REQ包继续向下一跳节点进行广播。 当dest接收到多个路由请求REQ并准备启动路由回复应答过程时，一方面，该节点通过对收到的REQ包进行分析，提取出部分信息并进行本地LocalNHTable相应字段信息的添加维护；另一方面，该节点将对比各REQ的路由跳数字段，选择路由跳数最小的正向路由为最优路径，并将对应REQ中的路由记录复制到路由应答包REP的路由记录中，同时该节点将自身发送REP包的消耗成本以〈dest, cost〉添加到REP的辅助记录中，开始启动路由回复应答过程。 3.2　路由回复应答过程 2 路由发现过程包括路由请求建立子过程和路由回复应答子过程。由3.1节可知， dest根据选择的最优正向路径，启动路由回复应答过程。当中间节点收到REP包后，该节点首先进行本地LocalNHTable相应字段信息的添加维护：“回复应答数据包类型”字段填充为REP，“接收数据包”字段和“转发数据包”字段填充为Y，“消耗成本”字段填充辅助记录中对应节点的消耗成本情况；然后，将自身发送REP包的消耗成本添加到REP的辅助记录中，并根据路由记录寻找反向路径的下一跳节点；最后，发送更新后的REP包。此过程重复进行直至源节点src，最终src根据路由建立过程中选择的最优路径，开始进行正常的通信过程。 3.3　联盟成员支付分配过程 2 本节介绍ICR算法中节点支付分配过程。由于各节点本地保存的LocalNHTable包含的都是周围邻居节点参与路由建立过程的相关信息（发送或转发数据包的情况），通过借鉴构建全局网络拓扑结构的思想，各个节点每隔周期 T 都将自身保存LocalNHTable的相关信息进行广播扩展。最终各个节点都能维护一张类似LocalNHTable的全局节点信息表GlobalNodeTable。网络中的节点（源节点src和非源节点）都可以根据该表的节点信息完成对自身支付情况的计算，得出自身实际可以获取的支付金额，而具体的支付分配过程则可以通过src委托第三方集中式VCC(virtual credit center) [ 19 19 , 20 20 , 21 21 , 22 22 ] 的方式进行实现（可以为每个节点建立初始账户，分配的支付金额可以通过账户之间的转账实现），也可以通过在正常通信过程中对各参与转发数据包的节点所需支付额度进行加密并通过发送控制消息来进行分布式实现。 4　 仿真与分析 1 4.1　仿真环境 2 本文在NS2仿真平台（下载地址： http://www.isi.edu/ http://www.isi.edu/ nsnam/ns/ ）中对ICR算法进行了具体的实现，并与其他经典的算法进行对比，以此来验证ICR算法的有效性。 本文的仿真环境设置如下：MAC层使用IEEE 802.11 b的分布式协调功能（distributed coordination function，DCF），移动模型采用Random Waypoint Model，采用固定比特率(constant bit rate，CBR)作为传输流量模型，发送数据包的速率为4 packet/s，每个数据包随机地从一个源节点发送到另一个随机目的节点，移动速度在0~20 m/s之间任意选择。到达目的节点后，经过一个暂停时间(0~200 s)再开始新的转发过程。仿真过程中建立的通信连接数为30，一共生成25种随机拓扑，每种情况对应5种随机拓扑，最后的数据为5种拓扑所产生数据的平均值。为了合理地计算出各个节点接收和转发数据包的成本信息，本文结合各个节点物理层的实际接收、转发和发送数据包的能量消耗，计算其成本开销情况。其他参数的设置如 表1 表1 所示。另外，在仿真过程中假定对支付分配中的参数设置如下 <math display="block" id="M83"><mi>α</mi><mtext>=</mtext><msub><mrow><mi>M</mi></mrow><mrow><mi mathvariant="normal">s</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">c</mi></mrow></msub><mtext>/</mtext><mtext>(</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">r</mi></mrow></msub><mtext>+</mtext><msub><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">f</mi></mrow></msub><mtext>)</mtext><mtext>-</mtext><mn mathvariant="normal">0.02</mn></math> http://notExist.jpg http://notExist.jpg 41.06333542 4.57200003 ， <math display="block" id="M84"><mi>β</mi><mtext>=</mtext><mi>α</mi><mtext>+</mtext><mn mathvariant="normal">0.05</mn></math> http://notExist.jpg http://notExist.jpg 20.23533440 3.89466667 本文采用文献[ 23 23 ]的方法构建网络拓扑结构，具体形成的拓扑结构如 图2 图2 所示。 图2 图2 (a)为网络拓扑初始状态，其中存在40个正常的善意节点和10个自私节点。 图2 图2 (b)为网络拓扑最终状态，网络中的节点全部为正常的善意节点。另外，本文对自私节点攻击进行如下假设：采用黑洞的攻击方式，自私节点以概率1丢弃接收到的数据包。 参数 意义 取值 Area/m×m 拓扑区域 1 000 <math id="M85"><mo>×</mo></math> 1 000 N 网络节点数 50 r/ m 节点传输半径 250 S/ m·s -1 移动节点最大移动速度 20 P/ B·packet -1 分组长度大小 512 T/ s 整个网络的仿真时间 200 M 网络中的自私节点数 1~30 M src 源节点的最大支付阈值 100 E/ J 节点的初始化能量 100 4.2　性能对比参数 2 为了验证ICR算法的性能，将ICR算法与经典的AODV算法 [ 1 1 ] 进行对比，并围绕以下5个参数进行性能分析： 1） 分组投递率：定义为目的节点接收到的数据包总数与源节点发送的数据包总数的比值。 2） 端到端的平均时延：主要由网络中所产生的路由查找时延、数据包在接口队列中的等待时延、传输时延及物理层的重传时延组成，以反映路由建立的有效性。具体计算公式如下 <math display="block" id="M86"><mi mathvariant="normal">端</mi><mi mathvariant="normal">到</mi><mi mathvariant="normal">端</mi><mi mathvariant="normal">的</mi><mi mathvariant="normal">平</mi><mi mathvariant="normal">均</mi><mi mathvariant="normal">时</mi><mi mathvariant="normal">延</mi><mtext>=</mtext><mover><mrow><munder><mrow><mtext>∑</mtext></mrow><mrow><mi>i</mi><mtext>=</mtext><mn mathvariant="normal">1</mn></mrow></munder></mrow><mrow><mi>n</mi></mrow></mover><mtext>(</mtext><mi mathvariant="normal">接</mi><mi mathvariant="normal">收</mi><mi mathvariant="normal">到</mi><mi mathvariant="normal">第</mi><mi>i</mi><mi mathvariant="normal">个</mi><mi mathvariant="normal">数</mi><mi mathvariant="normal">据</mi><mi mathvariant="normal">包</mi><mi mathvariant="normal">的</mi><mi mathvariant="normal">时</mi><mi mathvariant="normal">间</mi><mtext>-</mtext><mi mathvariant="normal">发</mi><mi mathvariant="normal">送</mi><mi mathvariant="normal">第</mi><mi>i</mi><mi mathvariant="normal">个</mi><mi mathvariant="normal">数</mi><mi mathvariant="normal">据</mi><mi mathvariant="normal">包</mi><mi mathvariant="normal">的</mi><mi mathvariant="normal">时</mi><mi mathvariant="normal">间</mi><mtext>)</mtext><mtext>/</mtext><mi>n</mi></math> http://notExist.jpg http://notExist.jpg 131.57199097 8.46666718 其中， n 表示为源节点总共发送数据包的个数。 3） 归一化路由开销：指单位时间内路由控制包的发送总数，它是网络拓扑结构变化率的函数。具体计算公式如下 3 <math display="block" id="M87"><mtable columnalign="left"><mtr><mtd><mi mathvariant="normal">归</mi><mi mathvariant="normal">一</mi><mi mathvariant="normal">化</mi><mi mathvariant="normal">路</mi><mi mathvariant="normal">由</mi><mi mathvariant="normal">开</mi><mi mathvariant="normal">销</mi><mtext>=</mtext></mtd></mtr><mtr><mtd><mfrac><mrow><mi mathvariant="normal">转</mi><mi mathvariant="normal">发</mi><mi mathvariant="normal">的</mi><mi mathvariant="normal">路</mi><mi mathvariant="normal">由</mi><mi mathvariant="normal">控</mi><mi mathvariant="normal">制</mi><mi mathvariant="normal">包</mi><mi mathvariant="normal">数</mi><mi mathvariant="normal">目</mi><mtext>+</mtext><mi mathvariant="normal">发</mi><mi mathvariant="normal">送</mi><mi mathvariant="normal">的</mi><mi mathvariant="normal">路</mi><mi mathvariant="normal">由</mi><mi mathvariant="normal">控</mi><mi mathvariant="normal">制</mi><mi mathvariant="normal">包</mi><mi mathvariant="normal">数</mi><mi mathvariant="normal">目</mi></mrow><mrow><mi mathvariant="normal">目</mi><mi mathvariant="normal">的</mi><mi mathvariant="normal">端</mi><mi mathvariant="normal">收</mi><mi mathvariant="normal">到</mi><mi mathvariant="normal">的</mi><mi mathvariant="normal">总</mi><mi mathvariant="normal">数</mi></mrow></mfrac></mtd></mtr></mtable></math> http://notExist.jpg http://notExist.jpg 79.67133331 13.80066681 4） 联盟支付分配总和：指在形成的联盟中所有节点获得的支付分配总和。 5） 中间节点转发数据包总数：指通过采用本文提出的支付模型后，网络中中间节点所转发的数据包数目。 另外，本文在仿真过程中根据自私节点所占比例的情况，对AODV算法进行标记，以区别表示，具体如下： 1） 当自私节点所占的比例为网络中总节点数的10%时，将此种情况下的AODV算法标记为AODV-10%的自私节点； 2） 当自私节点所占的比例为网络中总节点数的30%时，将此种情况下的AODV算法标记为AODV-30%的自私节点。 4.3　仿真结果 2 本文在不同仿真时间下对ICR算法、AODV-10%的自私节点和AODV-30%的自私节点在分组投递率、端到端的平均时延、归一化路由开销、联盟支付分配总和和中间节点转发数据包总数方面进行了性能对比。具体情况如 图3 图3 ~ 图8 图8 所示。 图3 图3 所示为3种算法在仿真时间从0 s到200 s之间的分组投递率对比情况。随着仿真时间的逐渐增加，3种算法的分组投递率呈现递增的趋势。 仿真时间为200 s时，ICR算法、AODV-10%的自私节点、AODV-30%的自私节点的分组投递率分别达到了96%、71%和68%。因此，从 图3 图3 所示整体递增趋势来看，ICR算法的分组投递率性能优于其他两种算法。这是由于ICR算法采用了联盟博弈中大联盟的思想，确保各个节点实现自身支付分配最大化，迫使联盟中的中间节点都表现出积极合作的行为，提高了网络分组投递率。 图4 图4 给出了不同仿真时间下3种算法端到端平均时延的对比情况。如 图4 图4 所示，随着网络仿真时间的不断增加，3种算法的时延总体呈递增趋势。相比较而言，ICR算法的整体时延开销较小，基本维持在10~27 ms之间变化；AODV-10%的自私节点和AODV-30%的自私节点的时延一直处于递增的趋势，AODV-10%的自私节点开销略低于AODV-30%的自私节点。导致此结果产生的原因为：AODV-10%的自私节点和AODV-30%的自私节点这两种算法由于网络本身存在部分自私节点，影响了网络正常通信的连通性，并且在路由建立的正常过程中，数据包产生了过多的时延开销。此外，由于网络仿真时间的逐渐递增，节点参与正常通信过程中的自身开销也随之增加，因此导致3种算法的时延开销也呈上升趋势。 不同仿真时间下3种算法归一化路由开销的对比情况如 图5 图5 所示。从 图5 图5 中可以看出：3种算法的路由开销总体呈递增变化（变化范围维持在4~10之间），在仿真时间为80 s时都出现了第一次波动较大的情况，且ICR算法的整体路由开销略小于其他两种算法的路由开销。产生此结果的原因与 图4 图4 类似：主要是因为ICR算法是基于FCG支付模型，实现了自私节点的支付分配最大化约束，使得自私节点表现出了积极合作的行为，因而没有由于自私节点的非合作行为而产生额外的路由开销，其主要开销为随着仿真时间的增加而产生的路由维护和更新的额外开销；其他两种算法中由于自私节点的不合作转发行为严重影响了正常通信的路由维持过程，整个网络不得不重新发起路由建立的过程，以避免自私节点加入到路由中，从而为维护新产生的路由而增加了过多的路由开销。 图6 图6 给出了3种算法的中间节点转发数据包总数随仿真时间变化的对比情况。如 图6 图6 所示，3种算法的中间节点转发数据包总数总体都呈现递增的趋势。ICR算法由于采用了本文所提出的FCG支付模型确保整个联盟处于稳定状态，使得网络中不存在自私节点，因此，整个网络中的节点都积极地参与数据包转发过程，即该算法对应的转发数据包总数是最多的。而其他两种算法由于网络中存在自私节点的不转发行为，导致其转发数据包的总数略低。 图7 图7 为通过两种对比算法与ICR算法计算得到的联盟支付分配总和随仿真时间的变化曲线。AODV-存在2个联盟和AODV-存在3个联盟这两种对比算法将联盟博弈理论应用于Ad hoc网络中，并通过AODV算法进行了具体实现，分别设定网络中存在2个联盟和3个联盟。如 图7 图7 所示，ICR算法是以联盟博弈中形成的大联盟具有稳定性作为先决条件，而迫使网络中节点均自愿加入到大联盟中且节点都能获得最优的支付分配，大联盟中的所有节点都很积极地参与合作，因此，该联盟中的节点形成的联盟支付分配是最大的。而两种对比算法存在如下情况：联盟中的节点根据自身获得的支付分配动态加入或离开不同的联盟，不同联盟合并和分裂等，联盟结构无法达到稳定的最终状态，因此这两种情况对应产生的联盟支付分配会持续动态变化，无法达到最终大联盟在稳定支付分配中取得的最大值。 为了进一步验证ICR算法的性能，将该算法与基于博弈论经典算法机制设计思想 [ 19 19 , 22 22 ] 而形成的经典算法Ad hoc-VCG [ 19 19 , 21 21 , 22 22 ] 和COMMIT [ 20 20 ] 进行了对比，分析不同自私节点所占比例对节点支付分配总和的影响，如 图8 图8 所示。从 图8 图8 中可以看出：随着自私节点所占比例的逐渐增加，节点支付分配总和相应逐渐减少。当自私节点比例达到50%时，Ad hoc-VCG算法和COMMIT算法的节点支付分配总和基本上都接近30，而ICR算法还维持在40以上。产生此变化的主要原因为：Ad hoc-VCG和COMMIT算法的核心是基于VCG机制原理确保激励所选择的最优路由中各个节点都是合作节点，使得这些合作节点获得的支付分配达到最大，并且都能满足支付的防策略性和防共谋性，从而实现节点参与数据包转发的积极性。显然，这两种算法达到的节点支付分配最大化受限于网络中的部分节点。而ICR算法的核心是基于所有节点参与形成的大联盟满足3个特性（个体理性、联盟理性和有效性）而构建的最优支付分配模型，也就是联盟中所有节点获得支付分配均达到最大化，从而确保大联盟结构的稳定性，以及大联盟中的节点之间都是合作的。 5　 结 语 1 本文首先将联盟博弈思想运用到Ad hoc网络中，建立了一种FCG支付模型，给出了转发联盟结构实现稳定性（满足联盟博弈最优核的特性）的约束条件，确保节点获得的支付分配最大化，使得节点都自愿加入到稳定的联盟中，以此达到激励节点合作的目的。然后，基于经典的按需路由算法思想对上述模型进行实现，提出ICR算法。最后，通过仿真实验验证ICR算法的有效性，并与其他经典算法（AODV、Ad hoc-VCG和COMMIT）进行了性能对比。仿真结果表明，相较于其他算法，ICR算法在分组投递率、端到端的平均时延、归一化路由开销、联盟支付分配总和及被中间节点转发数据包总数方面的性能均显著提高。在下一步的工作中，我们将在其他仿真条件下继续验证该模型的有效性，并将其延伸到多播路由协议和QoS保证中进行进一步研究。 参考文献 ZHANG C , ZHOU M C , YU M . Ad hoc network security: A review [J]. International Journal of Communication Systems , 2007 , 20 ( 8 ): 909 - 925 . DOI: 10.1002/dac.840 http://dx.doi.org/10.1002/dac.840 . Ad hoc network security: A review SAMIAN N , ZUKARNAIN Z A , SEAH W K G , et al . Cooperation stimulation mechanisms for wireless multihop networks: A survey [J]. Journal of Network and Computer Applications , 2015 , 54 : 88 - 106 . DOI: 10.1016/j.jnca.2015.04.012 http://dx.doi.org/10.1016/j.jnca.2015.04.012 . Cooperation stimulation mechanisms for wireless multihop networks: A survey FELEGYHAZI M , HUBAUX J P , BURYAN L . Nash equilibria of packet forwarding strategies in wireless Ad hoc networks [J]. IEEE Transaction on Mobile Computing , 2006 , 5 ( 5 ): 463 - 475 ． DOI: 10.1109/TMC.2006.68 http://dx.doi.org/10.1109/TMC.2006.68 . Nash equilibria of packet forwarding strategies in wireless Ad hoc networks ALTMAN E , KHERANI A . Non-cooperative forwarding in Ad-hoc networks [C]// International Conference on Research in Networking (LNCS 3462) . Heidelberg : Springer-Verlag , 2005 : 486 - 498 ． Non-cooperative forwarding in Ad-hoc networks ABDULLAH W ， HASAN M . A game theoretical approach for topology control in wireless Ad hoc networks with selfish nodes [J]. Wireless Personal Communication , 2017 , 96 ( 1 ): 249 - 263 . DOI: 10.1007/ s11277-017 -4165-8 http://dx.doi.org/10.1007/ s11277-017 -4165-8 . A game theoretical approach for topology control in wireless Ad hoc networks with selfish nodes SRINIVASAN V , NUGGEHALLI P . Cooperation in wireless Ad hoc networks [EB/OL]. [ 2018-03-05 ]. http://citeseerx .ist.psu.edu/viewdoc/download?doi=10.1.1.13.1646&rep=rep1&type=pdf http://citeseerx .ist.psu.edu/viewdoc/download?doi=10.1.1.13.1646&rep=rep1&type=pdf . Cooperation in wireless Ad hoc networks CHEN T T , ZHU L H , WU F , et al . Stimulating cooperation in vehicular Ad hoc networks: A coalitional game theoretic approach [J]. IEEE Transactions on Vehicular Technology , 2011 , 60 ( 2 ): 566 - 579 . DOI: 10.1109/ TVT.2010.2093587 http://dx.doi.org/10.1109/ TVT.2010.2093587 . Stimulating cooperation in vehicular Ad hoc networks: A coalitional game theoretic approach DUSIT N , WANG P , WALID S , et al . Coalition formation games for improving data delivery in delay tolerant networks [C]// 2010 IEEE Global Telecommunications Conference . New York : IEEE Press , 2010 : 1 - 5 . DOI: 10.1109/GLOCOM.2010. 5684271. Coalition formation games for improving data delivery in delay tolerant networks KHAJONPONG A , EKRAM H , DUSIT N . Cooperative packet delivery in hybrid wireless mobile networks: A coalitional game approach [J]. IEEE Transactions on Mobile Computing , 2013 , 12 ( 5 ): 840 - 854 . DOI: 10.1109/TMC.2012. 46 http://dx.doi.org/10.1109/TMC.2012. 46 . Cooperative packet delivery in hybrid wireless mobile networks: A coalitional game approach KHAJONPONG A , EKRAM H , DUSIT N . Coalition-based cooperative packet delivery under uncertainty: A dynamic bayesian coalitional game [J]. IEEE Transactions on Mobile Computing , 2013 , 12 ( 2 ): 371 - 385 . DOI: 10.1109/TMC.2011.251 http://dx.doi.org/10.1109/TMC.2011.251 . Coalition-based cooperative packet delivery under uncertainty: A dynamic bayesian coalitional game PU J W , LI C P , YU C S , et al . A coalitional game analysis for selfish packet-forwarding networks [C]// 2012 IEEE Wireless Communications and Networking Conference . New York : IEEE Press , 2012 : 80 - 85 . DOI:10.1109/WCNC. 2012. 6214483. A coalitional game analysis for selfish packet-forwarding networks WALID S , ZHU H , MÉROUANE D , et al . Coalitional game theory for communication networks [J]. IEEE Signal Processing Magazine , 2009 , 26 ( 5 ): 77 - 97 . DOI: 10.1109/ MSP. 2009.000000 http://dx.doi.org/10.1109/ MSP. 2009.000000 . Coalitional game theory for communication networks MASSIN R ， MARTRET C J L ， CIBLAT P , et al . A coalition formation game for distributed node clustering in mobile Ad hoc networks [J]. IEEE Transactions on Wireless Communication , 2017 , 16 ( 6 ): 3940 - 3952 . DOI: 10.1109/TWC. 2017.2690419 http://dx.doi.org/10.1109/TWC. 2017.2690419 . A coalition formation game for distributed node clustering in mobile Ad hoc networks SARKAR S , DATTA R . A game theoretic framework for stochastic multipath routing in self-organized MANETs [J]. Pervasive and Mobile Computing , 2017 , 39 : 117 - 134 . DOI: 10.1016 /j.pmcj.2016.09.008 http://dx.doi.org/10.1016 /j.pmcj.2016.09.008 . A game theoretic framework for stochastic multipath routing in self-organized MANETs 王博 , 黄传河 . Ad Hoc网络中一种基于防策略支付模型的安全激励合作算法 [J]. 计算机学报 , 2012 , 35 ( 7 ): 1370 - 1389 . DOI: 10.3724/SP.J.1016.2012.01370 http://dx.doi.org/10.3724/SP.J.1016.2012.01370 . Ad Hoc网络中一种基于防策略支付模型的安全激励合作算法 WANG B , HUANG C H . Secure incentive algorithm based on strategy-proof payment model for cooperation in Ad Hoc networks [J]. Chinese Journal of Computers , 2012 , 35 ( 7 ): 1370 - 1389 .DOI:10.3724/SP.J.1016.2012.01370 (Ch) . Secure incentive algorithm based on strategy-proof payment model for cooperation in Ad Hoc networks 王博 , 黄传河 , 杨文忠 ， 等 . Ad hoc网络中基于惩罚机制的激励合作转发模型 [J]. 计算机研究与发展 , 2011 , 48 ( 3 ): 398 - 406 . Ad hoc网络中基于惩罚机制的激励合作转发模型 WANG B , HUANG C H , YANG W Z , et al . An incentive-cooperative forwarding model based on punishment mechanism in wireless Ad hoc networks [J]. Journal of Computer Research and Development , 2011 , 48 ( 3 ): 398 - 406 (Ch) . An incentive-cooperative forwarding model based on punishment mechanism in wireless Ad hoc networks 王博 , 陈训逊 . Ad hoc网络中一种基于信任模型的机会路由算法 [J]. 通信学报 , 2013 , 34 ( 9 ): 92 - 104 . DOI: 10.3969 /j.issn.1000-436x.2013.09.012 http://dx.doi.org/10.3969 /j.issn.1000-436x.2013.09.012 . Ad hoc网络中一种基于信任模型的机会路由算法 WANG B , CHEN X X . Opportunistic routing algorithm based on trust model for Ad hoc network [J]. Journal on Communications , 2013 , 34 ( 9 ): 92 - 104 .DOI:10.3969/j.issn.1000-436x.2013.09.012 (Ch) . Opportunistic routing algorithm based on trust model for Ad hoc network 汪贤裕 , 肖玉明 . 博弈论及其应用 [M]. 北京 : 科学出版社 , 2008 : 160 - 219 . 博弈论及其应用 WANG X Y , XIAO Y M . Game Theory and Its Applications [M]. Beijing : Science Press , 2008 : 160-219(Ch) . Game Theory and Its Applications ANDEREGG L , EIDENBENZ S . Ad hoc-VCG: A truthful and cost-efficient routing protocol for mobile Ad hoc networks with selfish agents [C]// Mobicom’03 Proceedings of the 9th Annual International Conference on Mobile Computing and Networking . New York : ACM Press ， 2003 : 245 - 259 . DOI: 10.1145/938985.939011. Ad hoc-VCG: A truthful and cost-efficient routing protocol for mobile Ad hoc networks with selfish agents EIDENBENZ S , RESTA G , SANTI P . The COMMIT protocol for truthful and cost-efficient routing in Ad hoc networks with selfish nodes [J]. IEEE Transaction on Mobile Computing , 2008 , 7 ( 1 ): 19 - 33 . DOI: 10.1109/TMC.2007.1069 http://dx.doi.org/10.1109/TMC.2007.1069 . The COMMIT protocol for truthful and cost-efficient routing in Ad hoc networks with selfish nodes KARGAR M , GHODSI M . Truthful and secure routing in Ad hoc networks with malicious and selfish nodes [J]. International Journal of Security and Its Applications , 2009 , 3 ( 1 ): 117 - 128 . Truthful and secure routing in Ad hoc networks with malicious and selfish nodes WANG Y , SINGHAL M . On improving the efficiency of truthful routing in MANETs with selfish nodes [J]. Pervasive and Mobile Computing , 2007 , 3 ( 5 ): 537 - 559 . DOI: 10.1016 /j.pmcj.2007.02.001 http://dx.doi.org/10.1016 /j.pmcj.2007.02.001 . On improving the efficiency of truthful routing in MANETs with selfish nodes WAXMAN B M . Routing of multipoint connections [J]. IEEE Journal on Selected Areas in Communications , 1988 , 6 ( 9 ): 1617 - 1622 . DOI: 10.1109/49.12889 http://dx.doi.org/10.1109/49.12889 . Routing of multipoint connections 10.14188/j.1671-8836.2019.06.001 TP 393 A 1671-8836（2019）06-0527-11 WANG Bo,WANG Lihong,HUANG Chuanhe.Incentive Cooperation Routing Algorithm Based on Forwarding Coalitional Game Framework for Ad hoc Networks [J]. J. Wuhan Univ. （ Nat. Sci. Ed ）,2019,65(6):527-537. DOI:10.14188/j.1671-8836.2019.06.001(Ch). WANG Bo,WANG Lihong,HUANG Chuanhe.Incentive Cooperation Routing Algorithm Based on Forwarding Coalitional Game Framework for Ad hoc Networks [J].J. Wuhan Univ.（Nat. Sci. Ed）,2019,65(6):527-537. DOI:10.14188/j.1671-8836.2019.06.001(Ch). 王博,王丽宏,黄传河.Ad hoc网络中一种基于转发联盟博弈框架的激励合作路由算法[J].武汉大学学报（理学版）,2019,65(6):527-537. DOI:10.14188/j.1671-8836.2019.06.001 王博,王丽宏,黄传河.Ad hoc网络中一种基于转发联盟博弈框架的激励合作路由算法[J].武汉大学学报（理学版）,2019,65(6):527-537. DOI:10.14188/j.1671-8836.2019.06.001 国家重点研发计划(2016QY03D0504，2016YFB0801304)；国家自然科学基金项目(61300206) 2018-10-30 2019-12-24 2020-05-21 武汉大学学报（理学版） 6 65