基于动态规划的无线传感器网络的路由算法

基于动态规划的无线传感器网络的路由算法

余骞

余骞YUQian（广州科技贸易职业学院，广州511442）（GuangzhouVocationalCollegeofTechnology&Business，Guangzhou511442，China）

摘要院在无线传感器网络的研究中，其中一个重要的问题就是路由问题，在数据传送方面具有多跳的特点，表现这一特点的原理就是动态规划原理，借用此原理来设计传感器网络的路由算法显得最适合不过了。文章经过分析研究和测算，认为路由算法能最大限度的实现能量节省。

Abstract:Inthestudyofwirelesssensornetworks,theroutingproblemisoneofthemostimportantissues,whichhasamulti-hopcharacteristicintermsofdatatransmission.Dynamicprogrammingprincipleistoperformancethisfeature,andusingthisprincipletodesignsensornetworkroutingalgorithmismostsuitable.Afteranalysisandestimates,thispaperconsidersthatroutingalgorithmcanachievemaximumenergysavings.

关键词院路由；路由算法；无线传感器网络；跳数值Keywords:routing；routingalgorithm；wirelesssensornetworks；hopvalue中图分类号院TP393.1文献标识码院A文章编号院1006-4311（2014）06-0192-020引言随着社会通信技术的发展与进步，我国在传感器和计算技术方面有了突飞猛进的发展，当世界各国出现计算能力、感知能力的微型传感器，表明通信技术的发展已逐步全球化。我们所说的这个传感器网络可以感知和采集网络内的环境信息，还能实时的监测对方的信息，然后经过分析有效的传送到需求客户手中。这种网络的优势就在于他能在任何环境、任何地点、任何时间来获取大量的可靠信息。所以，其通常被应用于国家安全、国防军事以及交通、卫生和家庭等多个领域。

伴随着网络处理器的飞速发展，能够利用很少的成本产生大量的有效传感器节点，并且在某些特定区域内散播，从而形成无线传感器网络。随着这种技术的发展，使得管理和控制算法被急需，这同时也是对传感器网络发展的一个巨大的挑战，经过分析研究，大部分科学人员认为算法的核心就是传感器网络中的路由问题。

1无线传感器网络路由问题及其研究状况无线传感器网络的一个重要组成部分就是传感器，它通常包含信息处理单元、能量单元、感知单元以及信息交换单元，特殊的传感器还会包含移动器、位置定位系统和能量生成器等等。收集和感知数据是任何一个传感器所具备的基本功能，它通常通过多跳的方式向汇点传送信息，而后汇点通过网络与用户进行信息传递，同时任务管理中心也是运用这种方法为各个节点布置任务。

传感器的主要功能是信息的收集、处理以及传播，上文所讲的路由问题是在一定的指标背景下所存在的延迟、容错性、消耗水平、网络的寿命等等情况，要积极有效的改进汇点与源节点之间的信息疏导，要依据各个国家实际情况的不同制定不同的路由协议。路由协议可以分为多跳路由协议以及单跳路由协议，LEACH属于单跳路由协议，多跳路由协议则包含很多种，同时多跳路由协议也可分为多径路由和单径路由。我们通常所接触的rumor即为单径路由，Braided和MESH则为所径路由。我们在设计传感器路由的同时要考虑的关键问题就是传感器网络中能量是否有效，同时还要考虑它信息的可靠性。最近新提出的ACO（蚁群优化算法）是将如何对复杂组合进行优化这一问题作为首要解决问题的一种启发式算法。这种算法在实验中得到了较为满意的结果。

2基于动态规划的路由算法在研究决策的过程中，动态规划是最行之有效的一种方法。它的基本原则就是将M阶段过程的问题立即转化为M个单阶段的问题，然后运用不变嵌入原理进行求解，这是最为优化的一个战略。经实验证明，这种处理问题的方式是解决无线传感器网络路由问题的最优方法。

2.1传感器网络节点跳数生成算法和网络结构特点在实验中，我们一般用G=G（V，E，w）来表示带权重的连通图，它代表的是无线传感器网络，节点集—V，边集—E，w则代表一个费用值。V中的任何一个节点都代表着一个传感器，对于vk，vl沂V，ekl=（vk，vl）沂E仅仅代表vk，vl可以交互纤细。由于能量有限，并不是任何两个传感器都可以实现信息交互。

3最小跳数最小费用路由与最小费用路由之间的关系在传感器网络应用工程中，能量的消耗并不符合“三角不等式“，图1充分的描绘出了最小跳数最小费用的充要条件。

定理2：从图1可以看出，最小跳数最小费用路径的充要条件就是传感器网络一定满足“三角不等性“。

4能量消耗分析本章节研究算法的能量消耗。如果全部的传感器都具备同样的发射半径和感知半径，并且它的发射数据包消耗的能量和数据包的包长成正比，我们可以计算出，在动态规划背景下，三种路由算法都能改进能量消耗过快的情况，并且它比数据前传等路由算法所消耗的能量要小很多。

5结论最近几年，一些专家学者开始研究无线传感器网络，至今为止，路由问题仍然是其最为核心的问题，经过研究实验证明，数据传送多跳特点仍然是路由算法的最佳方式。因为传感器网络的网络环境是现实中具体的网络，所以想要设计一款通用的路由算法可谓是难上加难。我们要根据不同的具体应用，设计不同的路由算法。本文通过研究计算，给出了最小费用路径的一个充要的条件，但是，如何设计求解最小费用路径的具体路由算法，是我们下一步研究的方向。

参考文献院[1]裴莉.无线传感器网络应用综述[J].科技信息，2010（33）.[2]司海飞,杨忠,王琣.无线传感器网络研究现状与应用[J].机电工程，2011（01）.[3]肖军,李科,王建华.无线传感器网络通信与路由研究[J].电脑知识与技术，2008（18）.[4]夏少波,许娥.无线传感器网络WSN探究[J].通信技术，2010（08）.[5]邝自力,张伟,梁宏军.无线传感器网络及其应用[J].现代电子技术，2006（22）