| 标题 | 基于博弈论的无线传感器网络路由算法研究 |
| 范文 | 刘舒拉 摘 要：在通过博弈论概念建立网络模型的基础上，讨论了各种针对特定传感器网络特点的路由算法。归纳了基于博弈论的无线传感器网络路由算法的设计原则和分类方法。详细比较了这些算法的特点、性能差异和应用范围．最后对无线传感器网络路由算法的研究现状进行了总结，并指出未来的研究重点。 关键词：博弈论； 无线传感器网络； 路由算法;网络模型 中图分类号：TN92-34 文献标识码：A 文章编号：1004-373X(2011)09-0045-03 Game-theory Based Routing Algorithms for Wireless Sensor Network LIU Shu-la (Department of Electrical Engineering, Xian Aerotechnical College, Xian 710077, China) Abstract： The various routing algorithms aiming at the characteristics of the specific sensor network are discussed based on the introduction of the game theory concept to establish the network model. The design principle and classification method of routing algorithms for wireless sensor network are summarized. The characteristics, performance difference and application scope of the algorithms are compared in detail. The research status quo of wireless sensor network routing algorithms is described. The research focus of the future research is pointed out. Keywords： game-theory;wireless sensor network; routing algorithm; network model 0 引 言 由于无线传感器网络(WSNs)自身的体积、成本、重量和寿命等特点决定了无线传感器网络最主要的使用方向，再加上自身电源的有限性也限制了它们的计算以及之间的通信能力，因而需要在网络的可靠性和延长网络生存周期之间进行均衡。所以，设计合理的路由协议对降低及平衡网络中结点的能耗，延长网络的存活时间有着重要意义，同时也是WSNs网络协议研究的重中之重琜1]。 博弈论是一个相互依存的理论和不确定性条件下的决策。博弈论有三个组成部分：参与者集合，参与者行为集合，策略集合。当博弈执行时，一个参与者的策略就是一个完整的行动计划。参与者可以以自我为中心，以谋取最大利润。因此，一个参与者的分布式策略，往往可以提供一个优化的解决方案博弈琜2]。 本文研究了基于博弈论路由模型的建立方法。依照博弈论对结点问题的解决方法，以期帮助与解决无线传感器网络的问题。 1 博弈论模型下的无线传感网络路由算法 无线传感器网络中的一个关键问题是路由遥感数据的问题。无线传感器网络有效的路由选择算法包括减少多跳次数、簇状构造、定向扩散和随机化算法。然而，在中继结点之间有可能会有合理的干扰，中继结点通过拒绝参加从其他结点或其他网络的结点转发数据包来保存能量。这样，就可以通过提供激励来鼓励路由合作，以讨论博弈论在无线传感器网络中的应用［3］，如图1所示。 图1 博弈论在无线传感器网络中的应用分类 文献[4]用博弈论分析了一个博弈的结果，这些已部署的传感器属于不同的簇头，可以获得转发的合作激励。当传感器向属于不同簇头的传感器提出请求服务时，其他的传感器可以根据自身资源来选择支持或拒绝其请求。它完全可能会自私地拒绝提供支持，以保存自己的资源。在这样的博弈中，没有一方的簇有义务为其他簇的结点提供服务，纳什均衡的结果可确定其是否属于不同的簇的非合作结点。为了避免这样的情况出现，可使用令牌作为激励来鼓励属于不同簇的结点之间的合作。两个簇组织i∈{A,B}部署传感器{si1,si2,…,sik}可组成2K个矩形网络结点。令牌的使用可以促进每个簇在时间周期T内完成合作协议。当属于一个簇的结点a请求属于另一个簇的结点b帮助时，它可发送一个绑定令牌的请求。如果请求获准，结点b将接受令牌；否则，结点a仍然保留该令牌。一个实用的传感器结点的功能可由请求的数目由结点sik提供和接受，通信信号发送数量由sik负责，它可以提出请求的总数 ［5］。 一个可靠的路由，需要广泛选择同时协作数据汇聚工作的传感器结点数量，以增加网络信息量和通信资源以及能量消耗的有效合理利用。它们的算法以传感器为中心，并使用博弈论作为研究方法。在这个方法中，传感器作为合理优化合作，可以寻找最佳的网络架构，以实现传感器行为的最大化收益。传感器收益被定义为传感器行动的收益减去独自的损耗琜6-7]。 建立相关的能量存储路由是收益最大化的关键，一系列的传感器都是路由活动的参与者，当汇聚结点发送一个查询给这一系列传感器时，它可被用来检测结点匹配的遥感属性。通过用一个值vi来代表匹配程度可以抽象出这样的算法思想。如果vi=0，则意味该查询不匹配任何属性，这确保了高价值数据不惜成本通过可靠的多路径路由。发送结点通过选择最佳系列传感器可将数据传到接受结点。每个传感器结点建模作为中继接受数据包时，只有一个邻居结点，因此，形式上只有一个链路可以连接任意的源结点和目的结点。一个结点策略可以采用二进制向量形式{li1,li2,…,lin}，lii=1/0来代表一个传感器结点si选择发送或者不发送数据包给结点sj。由于每个接受数据的结点均可作为一个激励到汇聚结点，故其收益的一个可靠路径功能和信息的预期值也在该结点，这就决定了其理想的结果在数据汇聚树。如果一个传感器结点选择其他树的结点，则将导致次优行为，这会从其他结点减小收益。因此，这就形成了博弈的纳什均衡的可靠查询路由。由于网络不可靠，传感器网络会因整个网络目标最大化自己的收益。“路径弱点”的路径度量会评价各种次优路径。该路径的弱点决定了有多少结点获得偏离当前路径到最优路径。负偏差表明结点si更多地从策略和配置路径受益；正偏差意味着结点可以有更好的表现。它们也可以展现一组版本称之RQR，所有路径结点分享在路径上的最差结点的受益。而不是选择一个邻居结点，以便在原始博弈中最大化自己的收益。结点在TRQR模型中可以通过最大化收益来妥协。一个重要发现是在假设结点成功概率p∈(0,1]，并在结点i和j之间的路径损耗cij=c时，对于所有的i，j最可靠的路径就是RQR博弈均衡的路径。而对于均衡p，均衡路径也成为最简单路径(MCP)。在合理的网络目标情况下，结点希望自己的收益最大化，而TRQR则较低，因此其继承了在MRP网络中路径不可靠的缺陷。 2 博弈论的收益 相比于无线传感器网络中使用经典的博弈论来研究能量效率，在多级无线传感器网络中的数据包转发问题也可以适用改进的博弈论。改进的博弈论应用可以容许参与者采用预先设定好的行为和策略以及只使用本地信息［8］。 假定一个多级（异构）无线传感器网络中任意两个不相邻的两类可以通过多条路由通信，那么结点可以自主和通过它的活动链接来优化吞吐量并采取优化策略。结点如果多次参与与其他结点的博弈，那么在重复博弈中，结点在给定圈中的行为将受其他结点的影响。因而，重复博弈提供了一种方法来惩罚那些由于没有相互合作而减少了在博弈末期的收益的结点。这可以通过降低声誉和减少奖励来在博弈末期降低收益。合作的回报，可以通过检验在博弈末期的重复局数的收益来实现。努力提高合作时间的结点可以获得更高的声誉，更快的累积奖励将被包含在可靠路由中。每一级的簇结点可决定是否转发数据包。博弈结束时只有两类保持活跃，其中一级类结点被认为是无效结点将首先被消耗。 为了发展合作/叛离矩阵，引入激励合作机制，可在发送或转发数据包时，一类消耗电池能量β和获取激励γ，如果此类拒绝转发，它们将获得φ且同时没有成本。事实上，各类中的所有结点均可被假定为两种策略与编译：合作和缺陷。它们可从非合作参与者获得值α乘以合作结点数量的收益。有两种情况：在移动类之间转发数据包和包转发在空间分散的固定类。引进一个PG策略的方式如下：合作并继续合作直到其他结点缺陷n(n≥0)次，然后缺陷永久。该策略的收益是整个期间δ(0<δ<1)加权后的所有收益总和的加权。这表明是在静止类之间的数据转发。如果每个参与者均执行PG策略，则可以实现纳什均衡，此时的折现因子δ大致趋近于整体。对于固定类，形成簇后将获得合作稳定收益以及减少背叛剥离。相对于移动类，变异已经被证明是基于动力学进化的惟一的稳定收益。而对于移动类转发数据包，假定随着参与者合作的数量增加，合作收益也在增加。然而，在静止类中的收益稳定的战略合作则需依靠α，高值α甚至对固定类都是一个不稳定合作琜9]。这些结果可参见图2的总结。 图2 基于改进博弈论的WSNs静态和动态博弈的稳定收益 3 结 语 本文讨论了通过博弈论相关概念来解决无线传感器网络（WSNs）中的多种路由算法问题。总结了多种兼顾结点能量与结点分布的传感器网络路由算法。其中基于博弈论的无线传感器网络非均匀分簇节能路由算法［10］是一种比较高效节能的网络分簇算法。而其不足之处在于它随机选举簇首的方式破坏了网络的负载均衡性，而这可能会导致网络寿命的缩短和传输吞吐量的降低；基于博弈论的非均匀分簇策略，可以解决结点能耗分布不均的难题。 参考文献 ［1］TONG W T, CULLER D E. Taming the unde relying challenges of reliable multihop routing in sensor networks[C]//Proceedings of ACM SENSYS. Los Angeles, CA, USA: ACM, 2003: 14-27. ［2］范如国,韩民春.博弈论［M］.武汉:武汉大学出版社,2007. ［3］MILLER D, TILAK S, FOUNTAIN T. ″Token″ equilibria in sensor networks with multiple sponsors [C]// Proceedings of the Workshop on Stochasticity in Distributed Systems. San Jose, CA: WSDS, 2005: 5-13. ［4］KANNAN R, IYENGAR S S. Game-theoretic models for reliable pathlength and energy-constrained routing with data aggregation in wireless sensor networks [J]. IEEE Journal of Selected Areas in Communications, 2004, 2: 1141-1150. ［5］RAICU I. Local load balancing for globally efficient routing in wireless sensor networks [J]. International Journal of Distributed Sensor Networks, 2005, 1: 163-185. ［6］DAI H, HAN R. A node-centric load balancing algorithm for wireless sensor networks [C]// Proceedings of IEEE Global Communications Conference on Wireless Communications. [S.l.]: IEEE, 2003, 1: 548-552. ［7］CROSBY G V, PISSINOU N. Evolution of cooperation in multi-classwireless sensor networks [C]// Proceedings of the 32nd IEEE Conference on Local Computer Networks. [S.l.]: IEEE, 2007: 489-495. ［8］SADAGOPAN N, SINGH M, KRISHNAMACHARI B. Decentralized utility based sensor network design [J]. Journal of ACM Mobile Networks and Applications, 2006, 3: 341-350. ［9］HARVEY N J, LADNER R E, LOVASZ L, et al. Semi-matchings for bipartite graphs and load balancing [C]// Proceedings of Workshop of Algorithms and Data Structures. [S.l.]: WADS, 2003: 294-306. ［10］杨宁,田辉,黄平,等.基于博弈理论的无线传感器网络分布式节能路由算法［J］.电子与信息学报,2008,30(5):1230-1233. 注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文 |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。