Ad hoc网络中基于博弈论的激励合作路由算法研究

Due to the limited of energy, available bandwidth and computing capacity in Ad hoc networks, nodes always conserve their scare resources to show the selfish behavior. Therefore, it is necessary to design incentive mechanisms to improve the enthusiasm of cooperation among nodes. In recently years, game theory has become an important research tool which is useful for the researchers to design routing algorithms for Ad hoc networks. Moreover, game theory also involves the idea of enhancing the cooperation among the different players. In this project, we also use game theory to give the solutions to defend selfish behaviors, and give the research ideas from the two aspects of passive punishment mechanism and active incentive cooperation. On the one hand, we use passive punishment as an entry point. At first, we illustrate several general punishment strategies towards behavior of selfish nodes and derive the corresponding incentive cooperation forwarding conditions by using repeated game theory. Then, we establish a general punishment constraint mechanism and design an enhancing cooperative routing algorithm, thereby they can act as a deterrent to the behaviors of the non-cooperative game players and improve their cooperative enthusiasm for packet forwarding. On the other hand, we use active incentive cooperation as an entry point. Using the mechanism design theory to analyze and design node cooperation schemes is the inevitable trend of the future, so we firstly analyze the VCG mechanism based on algorithmic mechanism design. Then we design a new routing algorithm to force nodes to report their forwarding costs truthfully, so as to they can get their compensation which is more than their cost of forwarding packets. Therefore, it can stimulate nodes’ participating in the packet forwarding process. In a word, the proposed models and algorithms will provide an option guideline for avoid selfish nodes’ attacking and routing establishing of wireless multi-hop networks in the future.

Ad hoc网络由于受到自身能量、可用带宽和计算能力的限制，节点往往表现出自私性。因此，急需建立有效的激励机制来提高节点之间的合作性。近些年来，博弈论成为研究Ad hoc网络路由算法的一种重要工具。此外，由于博弈论中包含了许多增强博弈双方之间"合作性"的思想。因此，本课题拟基于此从两个方面展开研究。一方面，以"被动惩罚约束"为切入点：本课题鉴于重复博弈论思想，研究对非合作博弈方施加通用的惩罚约束条件，设计通用惩罚约束机制和增强合作路由算法，从而对非合作博弈方的行为起到一定的威慑作用，调动非合作博弈方的合作转发积极性。另一方面，以"主动激励合作"为切入点：本课题基于算法机制设计VCG的思想，研究某种机制迫使节点真实地报告自己的转发成本，设计激励合作路由算法，确保节点所获得的补偿大于其转发数据的成本开销，从而激励节点参与数据转发过程。总之，这两种思路在避免自私节点的攻击方面和路由建立提供了可行的方案。

由于Ad hoc 网络中的节点受到自身处理能力，存储空间和电池能量等各种资源的限制，节点往往会表现出自私行为，丢弃所要转发的数据包，从而降低网络的性能，因此如何增强这类节点的激励合作积极性成为当前Ad hoc网络研究的主要内容之一。.本项目通过借鉴博弈论中的经典思想和理论成果，创新性地运用到解决Ad hoc网络中节点的自私激励问题中，从而设计高效的激励合作路由算法，增强网络的安全性能。本项目的主要研究内容如下：.（1）提出基于联盟成员节点支付分配模型的激励合作路由算法ICR。本项目借鉴联盟博弈思想，针对节点之间数据包转发过程，定义了转发联盟博弈过程，建立了联盟成员节点支付分配模型，给出了为确保形成的大联盟为稳定核而要满足的约束条件，并基于上述模型提出了激励合作路由算法。.（2）提出基于离散时间马尔科夫链模型的转发联盟结构收敛方法。本项目也将节点之间数据包的转发过程定义为非重叠转发联盟博弈，建立了联盟成员中节点的收益模型，为了确保网络中所有节点的期望收益达到最大化，并设计了基于离散时间马尔科夫链的模型，使得网络中形成的转发联盟结构最终收敛为稳定的转发联盟结构，即使得网络中的所有节点都愿意参与到数据包的转发过程中，提高网络正常通信的协作性。.（3）提出基于重叠联盟博弈模型的分布式联盟形成算法OCF。本项目借鉴联盟博弈思想，假定网络中每个节点为了获得最大的支付而愿意同时加入至少一个合作联盟，为此，建立了重叠联盟形成博弈模型，提出了一种分布式联盟形成算法OCF，以求解最优的稳定联盟结构。并将此算法融入到现有Ad hoc网络的路由算法中进行实现，提高在路由建立过程中节点的合作积极性。.（4）提出基于防策略支付模型的安全激励合作算法ICTP。本项目借鉴博弈论中算法机制设计思想，建立一种防策略和防共谋攻击的支付模型，并将此模型融入到现有Ad hoc网络的路由算法中进行实现，从而增强通信的可靠性，减少通信过程中的开销。.（5）提出基于节点间关系成熟度度量的信任模型。本项目通过对节点间的信任关系进行度量来间接刻画节点的自私行为，提出了一种基于关系成熟度的信任模型和管理机制，并延伸至Ad hoc网络中路由协议中进行应用，以减少这类攻击行为对网络的影响。.综上所述，本项目在Ad hoc网络中路由协议和安全方面进行了相关的研究，取得了一定的研究成果，该项工作的研究具有很好的理论指导意义。