节能路由算法（共7篇）
节能路由算法 篇1
无线传感器网络是一种面向具体应用、以数据为中心、传感器节点资源有限、网络拓扑经常发生变化的大规模自组织网络。随着传感技术、微电子技术、嵌入式计算技术和通信技术的快速发展和高度集成, 它的应用前景也越来越广阔, 如:军事领域、防恐与反恐、环境监测与预报、空间探索、城市交通管理、智能家居等, 已逐渐深入到人类生活的各个领域, 被认为是对21世纪产生巨大影响力的技术之一[1]。传感器节点通常由能量有限的电池供电, 在目前的技术水平下, 通过提高电池的容量或人工更换电池的方式补充能源是不切实际的。因此, 对无线传感器网络路由算法的设计应当把节约能源放在首要位置, 综合考虑能量消耗的均衡性问题, 以达到最大限度的延长网络生命周期的目标。
对无线传感器网络的节能研究主要集中在硬件的设计、MAC协议及路由协议设计方面。目前提出的无线传感器网络路由协议主要有两类:平面路由协议和层次路由协议。传统的平面路由协议需要在每个节点中维护一张路由表, 通过节点之来的信息交换来实现路由的选择, 这样需要消耗大量的路由空间并增加了网络的通信负担。层次路由协议的基本思想是将网络分成多个簇, 由簇头节点对各自簇内的数据进行简单的处理并传输到sink节点, 这样簇头节点便成为分层路由协议中的瓶颈节点。采用基于分簇的层次路由算法相对平面路由算法具有更好的适应性和节能性[2]。文献[3]提出了DDCH算法, 利用由具有局部最大剩余能量的节点所构成的“能量核”来进行路由, 选择一条自源节点到目的节点的局部最短路径来进行数据的传输该算法具有较低的时间复杂度和较好的可扩展性文献[4]提出了DEEC算法, 从节点剩余能量及其与基站之间的距离为出发点, 提出按功能设置四种不同类型的节点, 除簇头节点外, 其余三种分别完成数据收集、数据处理、数据转发的功能。该算法能在较小的网络延迟下有效地延长网络的生命周期并均衡网络的能量消耗, 但增加了信息交换与数据传送的次数, 增加了额外的消耗能量。文献[5]提出了一种基于簇的多跳高效节能路由算法, 该算法中节点自主地根据其剩余能量来竞争簇头, 分簇完毕簇成员如果没有感知任务就处于休眠状态;簇头之间通过建立路由树以多跳方式将收集到的数据经根节点发送到sink节点。文献[6]对最小ID分簇算法进行了改进, 通过调整簇头节点的功率大小来增加或减少簇内节点的数量, 以达到最佳的网络性能。文献[7]提出了一种基于LEACH的固定聚类路由算法。
本文在基于LEACH的固定聚类路由算法的基础上结合已有的研究, 提出了一种新的节能的分簇路由算法, 其基本思想是在簇头节点的选举过程中引入了“捎带”技术以减少网络的通信流量, 降低延时;簇头节点之间通过构造邻节点的路由表并选择具有较大剩余能量值、通信距离较短的路径将数据发送到基站, 以实现使能量的消耗均衡的目的, 从而延长网络的生命周期。理论分析和仿真结果表明, 该算法是可行的并表现出更好的性能。
1 一种节能的分簇路由算法
1.1 相关工作及问题分析
基于LEACH的固定聚类路由算法的是以聚类的方式来组织节点的, 其基本思想为: (1) 根据被监测区域的面积以及传感器节点的总数目, 通过数学计算得到固定聚类路由算法的最优聚类首领数; (2) 根据节点的地理位置信息及最优聚类首领数, 由BS统一将被监测区域划分为面积大体一致的固定聚类区域; (3) 聚类区域一旦划定便固定下来, 从第二轮开始由具有最大剩余能量值的节点担任聚类首领; (4) 聚类内节点采用单跳的方式与聚类首领通信; (5) 聚类首领之间通过建立路由树, 形成层次化聚类结构与BS进行通信。
该路由算法可以延长网络的生命周期, 并在一定程度上均衡了能量的消耗。但是在步骤 (3) 聚类首领的选举过程中, 聚类内的所有节点将自己的当前能量值与阈值相比较, 若大于阈值, 则向前一轮的聚类首领报告自身的能量值, 再由前一轮的聚类首领选定具有最大剩余能量值的节点担任聚类首领, 并将信息广播给聚类内的所有节点。该过程进行了一轮计算机和两轮额外的信息传输, 虽然减少了需要传输信息的节点的数量, 但还是增加了通信的流量和能量的消耗。步骤 (5) 聚类首领通过比较自身和其它聚类首领的剩余能量值, 选择具有最大剩余能量值的聚类首领作为其父节点的方式建立路由树。该过程忽略了节点之间的距离信息。由于通信损耗能量同传送的数据量和到达目标的距离平方成正比, 在通信方式上, 一般认为短距离的无线低功率通信技术最适合传感器网络使用[8]。
1.2 算法模型和假设
本文中采用二层架构模型。上层为簇头节点层, 主要负责通过簇头之间的路由表选择最佳的转发路径将簇内收集的数据发送给基站以及下一轮簇头节点的选举;下层是簇内节点层, 主要负责完成数据的收集任务。本文在该模型中做如下假设:
(1) 网络中所有的节点功能都是一致的 (即簇内所有的节点是平等的) ;
(2) 每个节点均有一个固定的ID号, 并且具有获取本身当前剩余能量值的能力;
(3) 所有节点具有感知自身地理位置及路由的功能;
(4) 初始状态各节点的能量是相同的;
(5) 被监测区域面积及传感器节点的数目是已知的。
1.3 算法详细描述
本文所提出的节能的分簇路由算法其基本思想为:将节点分成簇内节点与簇头节点两级拓扑结构, 簇内节点负责某个具体区域内的数据采集任务, 簇头节点负责将本簇内的数据进行必要的处理并传送给基站。固定的分簇及第一轮簇头的选举在初始阶段由基站完成, 其余簇头节点的选举依据最大剩余能量值的原则通过在簇内节点的最后一个数据包中“捎带”自身剩余能量信息竞争完成, 簇头节点之间形成网状拓扑结构, 并维持一张由邻居节点梯度、距离及剩余能量值组成的权值路由表, 通过选择权值最小的路径进行数据的传输。
算法描述为如下步骤:
Step1:在监测面积 (a×a) 和传感器节点总数
(N) 已经确定的情况下, 由公式推导出最优的分簇数, 其中LBS表示节点与基站之间的距离, λ为无线信号传播参数;
Step2:基站根据已经推导出的最优分簇数把被监测区域划分成k个固定的分簇, 并随机的为每个簇指定一个簇头节点;
Step3:成为簇头的节点发送一个消息给基站, 基站根据接收到信号的时间先后及强度给每个节点返回一个梯度值, 建立一个梯度场, 如下图1所示;
Step4:每个簇头节点在一跳的范围内 (邻节点) 建立一张路由表, 保存其邻节点的梯度值、当前剩余能量值、两节点之间的距离等信息, 其格式如表1。
簇头节点以一定的功率发送消息给它周围一跳范围内的邻居节点, 邻居节点收到消息后返回一个包含自身ID号、梯度值及当前剩余能量值的消息给该簇头节点, 簇头节点根据收到消息的时间及强度判断与邻居节点的距离, 并按上表设计的格式将信息存储在路由表中;
Step5:簇内节点将收集到的数据在自己的时间间隙内发送给簇头节点, 在簇头节点进行必要的数据融合等处理后发送给基站。由于网络内节点密度大导致同一分簇区域内数据的相关性与冗余性比较大, 数据融合技术是指在数据收集的过程中, 利用节点本地计算机和存储能力对数据进行操作, 去掉冗余信息, 达到减少通信量, 节约能量的目的;
Step6:簇头节点向基站发送信息时首先在路由表中找出所有梯度值比自己小的邻节点, 然后将其当前剩余能量值与一个参考量ξ进行判断, 若该值小于ξ则不再考虑将数据转发至此邻节点, 若该值大于ξ再根据两节点间的距离进行选择。节点之间的距离可以转化为它们之间响应的时间长短及信号的强弱, 距离越近, 响应时间越短, 信号越强。簇头节点选择距离较近的邻节点进行数据的发送。
Step7:数据发送完成后进行下一轮的簇头节点的选举。上一轮中簇内节点在发送最后一个数据包的时候将自身的当前剩余能量值插入到数据包的尾部进行“捎带”传送, 簇头节点通过判断提取出它们的当前剩余能量值并进行比较, 选择具有最大当前剩余能量值的簇内节点成为下一轮的簇头节点, 并将自己的梯度值嵌入到通知包中发送给下一轮的头节点;如果簇内节点的当前剩余能量均小于簇头节点, 则簇头节点继续担当下一轮的簇头节点;最后一个数据色的结构如表2;
Step8:返回step4重复执行, 直到网络内大部分的节点因能量耗尽而失效, 那么网络也就死亡。
2 仿真实验及性能分析
为了更好、更准确的评价本文所提出的节能的分簇路由算法, 本文设计了以下场景, 并从节点的死亡率与算法轮数的关系以及节点数据发送量与能量消耗之间的关系两方对其性能进行了分析。
无线传感器网络由200个传感器节点组成, 节点随机分布在被监测区域面积大小为100m×100m的区域内, 基站位于坐标为 (50, 100) 的位置。节点初始能量1.5J, 数据包长度500Bytes, 发送和接收数据的能量消耗为50nJ/bit, 放大电路功耗为100pJ/bit·m-2。
从图4 (a) 实验结果可以看出, 由于本文中所提出的分簇路由算法在簇头节点之间通过构造路由表并选择最佳路径进行数据的发送, 第一个节点的死亡时间比基于LEACH的固定聚类路由算法有明显的延迟, 节点全部死亡的时间也有明显的延迟。这说明本文中所提出的算法能更有效的延长网络的生命周期, 使能量的消耗更加均匀的分配到所有节点上。
从图4 (b) 的实验结果可以看出, 由于本文中所提出的分簇路由算法使用了最后一个数据包“捎带”节点当前剩余能量值的技术, 减小了网络中的通信流量, 所以算法的能量有效率相对于基于LEACH的固定聚类路由算法来说有明显提高。这表明本文中所提出的算法能够更加有效的利用能量, 更好的实现了能量的节约。
3 结论
本文所提出的分簇路由算法在簇头节点的选举方面主要考虑了通过减少网络的通信流量来达到减少开销, 节约能量的目的;簇内节点将数据发送到簇头节点后进行必要的数据融合, 去掉冗余的信息;簇头节点到基站之间的数据通过构造路由表并选择一条最佳路径进行发送。仿真实验结果表明, 本算法能有效的提高能量的使用效率, 达到节约能量, 均衡能量消耗, 延长网络生命周期的目的, 具有较好的性能。
参考文献
[1]崔莉, 鞠海玲, 苗勇, 等.无线传感器网络研究进展.计算机研究与发展, 2005;42 (1) :163—174
[2]梁英, 曾鹏, 于海斌.无线传感器网络中一种能量自适应的簇首选择机制.信息与控制, 2006;2 (35) :141—146
[3]林亚平, 王雷, 陈宇, 等.传感器网络中一种分布式数据汇聚层次路由算法.电子学报, 2004;11 (32) :1801—1805
[4]孙国栋, 廖明宏.一个用于传感器网络的分布式节能组簇方法.哈尔滨工业大学学报, 2006;9 (38) :1431—1435
[5]Lindsey S, Raghavendra C S.PEGASIS:powerful-efficient gathering in sensor information systems.GregRichardson.2002IEEEAerospace Conference Proceedings.Big Sky, MT, USA:IEEE Computer Society, 2002:9—16
[6]赵静, 陈向东.通过功率控制建立密度自适应的分簇无线传感器网络.传感技术学报, 2006;6 (19) :2751—2759
[7]肖伟茂, 王力.一种基于LEACH的无线传感器网络路由算法[硕士学位论文].陕西西安:西安电子科技大学, 2006
[8]任丰原, 黄海宁, 林闯.无线传感器网络.软件学报, 2003;14 (7) :1282—1291
[9]杜玉红, 张晓敏.无线传感器网络分簇算法研究:[硕士学位论文].山东济南:山东大学, 2007
节能路由算法 篇2
在无线传感器网络WSN中，由于各个节点的电量是有限的，而且想要对分散的节点进行充电或更换电池比较难以实现，因此选择一种合理的路由协议，降低网络各个节点的能耗，延长整个WSN的生存时间是当前WSN的主要研究方向之一。
一般来说WSN路由算法主要分为两大方面，一是平面路由算法，包括Flooding路由协议和Gossiping协议[1],MTE算法[2]等;另一种是分簇路由算法，包括LEACH协议[3],HEED协议[4],PEGAGIS协议[5]等。在平面路由算法中的各个节点地位都是相同的，没有等级和层次的限制，因此平面路由算法拥有组建简单，易于扩展，网络健壮等特点。与此同时，也造成了它灵敏性较弱，网络生存时间较短等缺点。在分簇路由中，WSN通常会被划分为多个簇，每个簇都相当于一个小型的WSN，最后由每个簇的簇头将信息传输给基站。分簇路由算法通过数据融合，集中传送的方法，有效地减小信息的传输量，大大减小了能量的消耗，从而延长了网络的生存周期。
由于分簇路由协议较平面路由协议相比，能有效地解决节点能耗过高，生存时间较短的问题;使得整个WSN灵活性增强，适合大规模网络的组建和扩展;分簇路由算法中动态成簇的思想，大大提高了网络的鲁棒性。LEACH协议作为分簇路由协议的基础，许多分簇协议也正是通过该协议演变而来，因此该协议具有极强的研究价值，本文对LEACH协议的算法进行了研究和改进，尽量使整个网络的能耗趋于平衡，延长网络节点的工作时间，进而延长WSN的生存时间[6]。
1 LEACH协议
LEACH协议[3]是由MIT的Heinzelman等人在2000年时提出的低功耗自适应分层路由协议，它是无线传感器网络中第一个被提出的分簇路由算法，在无线传感器路由算法的研究中有非常重要的位置[7]。
LEACH算法的过程主要分为成簇阶段和数据传输阶段，而将两个过程和起来称之为“轮”。在成簇阶段，节点会选择一个0至1的随机数，如果该随机数小于当前设定的阈值T(n)[3]时，该节点被选为簇头。T(n)[3]的公式为:
式中，P为整个WSN中簇头个数与节点总数的比值;r为当前所进行的“轮”数;G为近期1/P轮中未当选过簇头的节点集合。根据公式，在第0“轮”中，所有节点成为簇头的概率都为P，当选过簇头的节点，在之后的“轮”中不会再被选为簇头。经过1/P“轮”后，所有节点又会以P概率成为簇头。
当簇头选定后，簇头节点会向周围所有节点发送成簇广播，在WSN中的所有非簇头节点均会收到一个或多个成簇广播，他们会通过接收到信息的强度，来判定与哪个簇头成簇。最后，非簇头节点会发送一个“Join”信息至对应的簇头，成簇阶段完成。
在WSN完成分簇后，每个簇的簇头会给自己的簇分配TD-MA间隙，规定了簇内各个节点在该“轮”内的数据传输时段和休眠时段。簇内节点根据TDMA，在自己的时间段内向簇头传送信息，簇头节点在接收所有的非簇头节点的信息并进行数据融合后，将数据集中发送给基站BS。至此，LEACH协议中的一“轮”的工作完成[8]。
通过对LEACH路由协议的详细介绍，我们可以了解到，LEACH协议作为无线传感器网络中首个分簇路由算法，有着之前平面路由算法无法比拟的优势。它通过成簇，减少了网络中节点长距离传输数据的次数，进而减少了能耗。在每个簇的信息集中在其所属簇头后，簇头将集中的数据进行数据融合操作，减少了整个WSN的数据传输总量，达到减少能耗，延长网络寿命的目的[9]。但是LEACH协议也无法避免的存在着缺陷。由于LEACH协议在簇头的选区方面是随机产生的，并没有能对节能的剩余能量进行考虑，当某些剩余能量较少的节点被选成簇头后，大量数据的长距离传送会加速该节点的死亡。在一个节点死亡后，其周围的节点工作量随之加大，也加速了周围节点的死亡，进而缩短整个无线传感器网络的生存时间。在之后的一些基于LEACH协议的改进算法中，加入了节点剩余能量的因素，但仅仅考虑了单个节点的剩余能量，没有将地理位置对节点剩余能量的影响考虑其中。因此在无线传感器网络中，靠近基站的节点往往剩余能量较多，成为簇头的概率也相对较高，这样会造成网络簇头分布过于集中，这样不但没能体现出分簇路由协议的节能效果，反而增加了网络能耗负载，加速网络的死亡。
针对上述缺陷，提出了一种LEACH协议的改进算法。
2 改进的基于LEACH协议的节能算法
2.1 EB-LEACH算法思路
EB-LEACH算法的主要思想，是使无线传感器网络中的簇头分布更为合理，均衡网络中所有节点的能耗，从而实现延长无线传感器网络的寿命。
在分簇路由协议中，最重要的就是对簇头节点的选举，需要充分考虑其剩余能量以及节点位置。因此，在改进算法中将节点的剩余能量分为两个因素，分别为绝对剩余能量和相对剩余能量。绝对剩余能量是就网络全域而言的，即网络中节点的实际剩余能量;相对剩余能量是就簇内节点而言，即网络中各个簇内节点的剩余能量。在无线传感器网络节点工作中，距离基站远的节点因传输距离长，能耗较多，剩余能量普遍较距离基站近的节点少，因此仅从剩余能量方面决定簇头的选举，容易造成簇头过于集中。在引入了相对剩余能量后，针对距离基站较远，剩余能量较周边节点多的节点，也同样容易成为簇头，这样便使得簇头的分布更加均匀。
通过使剩余能量相对较多的簇头节点均匀分布，达到均衡网络节点能耗，最终实现延长网络工作时间的目的。
2.2 EB-LEACH算法描述
因为影响节点成簇的因素有多种多样，针对LEACH协议及其改进算法中的不足之处，单纯的选择剩余能量大的节点成为簇头，容易造成在网络运行一段时间后，簇头选定位置相对集中，进而造成网络节点的能耗过大[10]。
在无线传感器网络运行过程中，假设网络中有N各节点，随机分布在面积为M的区域之中，其中有K个簇头节点，因此平均一个簇中有N/K-1个节点，当网络中节点足够多时，N/K-1=N/K，融合一个单位数据的能耗为EDA，数据融合率为q，消息长度为l，数据长度为L，由于数据长度远大于消息长度，因此(1+L)=L。在网络一轮的工作中，首先在成簇阶段，簇头节点发送广播宣布成为簇头，在接收到其他节点发送过来的入簇消息后，向其发送簇内节点确认消息。在数据传输阶段，簇头依次接收簇内节点传输的数据后进行数据融合，最后将收集到的数据发送给基站[11]。因此簇头的能耗为:
作为普通节点，在接收到簇头节点发来的广播后，根据能量判断加入某个簇，并向该簇头发送入簇消息，在接收到簇头发送过来的确认消息后，簇内节点根据确认消息里的时间安排，在某个时间段内向簇头发送数据。因此簇中每个节点的能耗为:
综上所述，因此一个簇中所有节点在一轮中的能耗为:
因此改进的EB-LEACH算法在选举簇头时，加入了能量因子参数，充分地将节点的能量因素考虑在内。通过簇头间传输能量信息，掌握网络的全局能量情况。再通过簇内发送TDMA调度信息时，将能量信息一起发送给簇内成员，掌握网络局部能量情况，让所有节点都获取到其他节点的能量信息。通过网络对节点的能量分析，让剩余能量较多的节点更容易成为簇头，同时也使距基站较远且剩余能量较周围节点多的节点更容易成为簇头。这样不仅能使剩余能量较多的节点更容易成为簇头，同时也能使簇头节点均匀分布。从而使得网络各个节点能耗趋于平衡，大幅度增加节点的工作时间，实现延长网络生存时间的目的。改进后的算法簇头选举流程如图1所示。
通过算法改进，如果当前节点的剩余能量较大，则增加阈值T(n)，使之更容易成为簇头，反之则降低阈值T(n);如果当前节点距离基站较远且剩余能量较周围节点更多，则增加其阈值T(n)，提高其成为簇头的几率，反之则降低阈值T(n)。T(n)的具体公式为:
其中P为百分数，表示整个网络中簇头个数与节点总数的比值;r为当前“轮”数，表示现在正在进行的“轮”数;Ecurrent(r)表示当前节点的剩余能量;Eaverage(r)表示当前网络中所有节点的平均能量;EC-average(r)表示当前网络中其中一个簇内所有节点的平均能量;Eused(r-1)为上一“轮”中节点的使用的能量;α和β为能量平衡因子，其中α+β=1且节点距基站越远，β所占比例越大;G为节点集合，表示近期1/P轮中未当选过簇头的节点集合。
2.3 最优簇头数改进
为了进一步减少网络能耗，可以通过优化网络中的簇头个数，合理分配网络中簇的分布。根据之前推导的能量模型，在一个面积为M的区域之中，有K个簇头节点。根据式(4)中一个簇中所有节点在一轮中的能耗，可以推算整个网络，即K个簇在一轮中的能耗公式为:
为求出簇头数K的最优值，同时将公式两端对K求导，即:
令式(8)等于零，求解得出最优簇头数K值为:
2.4 改进算法复杂度分析
当网络节点数为n时，就空间复杂度而言，由于是n个网络节点同时工作，因此LEACH协议与EB-LEACH协议的空间复杂度均为O(n)。就时间复杂度而言，LEACH算法成簇阶段的时间复杂度O(n)。在EB-LEACH算法中，由于簇头间需要传输能量信息，增加了其时间消耗，因此其时间复杂度为O(n(1+p))。在网络足够大时，既n较大时，可近似的认为LEACH协议与EB-LEACH协议的时间复杂度相同。
3 仿真实验和结果分析
在Matlab仿真工具环境下，设置仿真实验参数如表1所示。
根据上述参数，分别对基于LEACH协议，LEACH-NEW协议和EB-LEACH协议的路由算法进行仿真实验，主要对这三种算法在工作中的网络存活节点数，节点能耗数等方面进行数据比较分析。图2为无线传感器网络拓扑图。在面积为100 m×100 m的区域中，随机分布了100个网络节点，图中以“o”表示，基站BS位于零点，坐标为(0,0)。上述三种算法均在该拓扑图中运行。
为了展示三种算法的网络生存时间，列出了在1000轮工作时间内三种算法的网络剩余活节点的变化曲线，随着工作轮数的不断推进，网络中的活节点数也将不断减少。如图3所示。
从图3中可以看到，在相同的网络节点拓扑图下，基于EB-LEACH协议的路由算法第一个死亡节点出现在第489轮，最后一个死亡节点出现在863轮，网络整体生存时间比其他两种协议更为持久。与之前改进的算法LEACH-NEW协议相比，EB-LEACH协议不仅拥有生存时间的优势，而且从600至700轮间的曲线斜率可以明显得出，EB-LEACH协议中节点的死亡速度也更为缓慢。由此可说明基于EB-LEACH协议的路由算法的网络节点存活时间明显优于使用其他两个协议的路由算法。
为了比较三种算法在工作中的能耗情况，给出了三种算法的网络在每一轮中所有节点剩余能量的总和变化曲线，随着工作轮数的不断推进，网络中的能量总数将不断减少。如图4所示。
从图4中可以看到，随着无线传感器网络的工作不断推进，网络中的死亡节点不断增多，能量消耗不断增大，剩余能量逐渐变小。但通过对比可以明显看出，使用EB-LEACH协议的路由算法直至863轮时才耗尽所有节点能量，且从网络一开始工作其能耗就明显少于其他两种协议。截取200至400轮间的网络剩余能量变化情况进行分析，不难发现基于EB-LEACH协议的路由算法的剩余能量较多，并且能量差距不断加大，通过求导可计算其能耗曲线斜率近似于0.08，小于LEACH-NEW协议曲线斜率的0.09和LEACH协议曲线斜率的0.1。这说明经过改进后的EB-LEACH协议中，网络每一轮工作的能耗始终低于另外两种协议的能耗。
除了剩余活节点与剩余节点能量的比较外，改进后的EB-LEACH协议在其它方面也普遍优于其他算法。表2列出了三种协议的死亡节点时间，数据包发送量，数据包平均能耗的比较结果。
通过表2的数据比较可以看出，EB-LEACH协议不仅在网络生存时间上优于另外两种协议，在网络数据传输中，由于延长了网络节点的生存时间，有效数据包传输数量也远高于另外两种协议。从数据包平均能耗可以看出，EB-LEACH协议不仅提升了网络数据包的发送成功率，同时降低了发送数据所需能耗，实现了降低网络能耗，延长网络生存时间的目的。
4 结语
本文对传统的LEACH协议进行了研究和分析，针对协议存在的不足之处进行了改进，提出了EB-LEACH协议。EB-LEACH协议改进了簇头选择方式，将节点剩余能量与地理位置分布相结合，对簇头节点选择条件进行了优化，使无线传感器网络中的簇头分布更为合理。在相同的拓扑图下对基于LEACH协议，LEACH-NEW协议和EB-LEACH协议的路由算法进行了仿真对比实验，实验结果也说明改进后的基于EB-LEACH协议的路由算法第一个和最后一个死亡节点出现时间晚于另外两种算法，网络工作时间比其他两种协议更为持久。此外，通过各项数据的对比也说明了改进后的算法在提高网络数据包的发送成功率的同时也降低了发送数据所需能耗，有效地降低了整个网络的能耗，提高了无线传感器网络的性能。
参考文献
[1]Zygmunt J H,Joseph Y H,LI L.Gossip-based Ad hoc routing[C]//Proc of IEEE INFOCOM.New York:IEEE Communications Society,2002:1707-1716.
[2]Zhao J C,Ahmet T E,Tughrul A.A Novel Application Specific Network Protocol for Wireless Sensor Networks[J].Circuits and Systems,2005:5894-5897.
[3]Wendi R H,Anantha C,Hari B.Energy efficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd Hawaii International Conference on System Sciences,2000:3005-3014.
[4]Ossama Y,Sonia F.HEED:A hybrid,energy efficient,distributed clestering approach for ad-hoc networks[J].IEEE Transactions on mobile Computing,2004,3(4):660-669.
[5]Stephanie L,Cauligi S R.PEGASIS:Power-Efficient Gathering in Sensor Information Systems[C]//Proceeding of the IEEE Aerospace Conference Big sky,2002,3:1125-1130.
[6]刘明,曹建农,陈贵海,等.EADEEG:能量感知的无线传感器网络数据收集协议[J].软件学报,2007,18(5):1092-1109.
[7]尚凤军.无线传感器网络通信协议[M].北京:电子工业出版社,2011.
[8]施叶玲,陈彬兵.无线传感器网络改进的LEACH-ID算法[J].计算机应用,2011,31(2):324-327.
[9]钟斌,邬毅松,李思敏.一种新颖的LEACH簇头选举算法[J].计算机系统应用,2011,20(2):216-218.
[10]王林,赵绍英.无线传感器网络LEACH路由协议的研究与改进[J].计算机工程与应用,2012,48(2):80-82.
[11]韩万强,刘云.WSN中基于分簇的改进路由协议[J].计算机工程,2012,38(5):105-107.
节能路由算法 篇3
网络路由有多种分类, 按网络性质可分为多计算机系统路由、有线网络路由和无线网络路由, 大约十年前, 计算机学者们热衷于计算机系统路由, 针对一种特定的拓扑结构, 例如超立方体、网格 (mesh) , 在某些节点或链路故障的情况下寻找最优通路.网络路由按通信方式分, 可以分为单播路由 (即端到端的路由) 、多播路由 (即端到目的节点集中的每一个节点的路由) 及Any cast路由 (即端到目的节点集中的任一个节点的路由) , 网络路由按路由算法来分, 可以分为源路由算法、分布式路由算法和分级路由算法.源路由算法假定每个节点了解整个网络的全局状态, 全局状态用链路状态协议通过广播获得, 或用距离向量协议, 用邻节点周期性交换距离向量获得, 当要发送消息时, 源节点就决定了整条路径, 而分布式路由算法假定每个节点只了解它的邻节点的情况, 即网络局部状态, 包括排队延迟、传播延迟、剩余带宽等, 根据路径的要求, 只决定下一跳应走向哪里.而分级路由算法假定网络节点分级, 每个节点了解聚合的全局状态, 即自己所在范围内的情况, 而对远处的上级节点只了解大致情况, 即每一物理节点保持聚合的网络影像。
2 WIA-P A网络概念及现状
中国自主研发的用于工业过程自动化的工业无线网络WIA-PA (wireless net works for industrial automation-process automation) 规范, 通过国际电工委员会IEC全体成员国投票, 成为第二个被承认的相关国际标准。工业无线网络工作环境恶劣, 需要网络具备较高的可靠性和实时性, WIA-PA采取了星型结构和MESH结构。相结合的两层网络拓扑结构, 第一层是MESH结构, 由网关设备和路由设备、冗余路由设备构成;第二层是星型结构, 由路由设备与现场设备或手持设备构成, 其中现场设备和手持设备不具备路由功能, 应用WIA-PA规范的网络则具有干扰因素较多, 拓扑稳定等特点。
针对MESH结构的无线网络, 现有主要路由协议是基于位置和以数据为中心的, 基于路由协议GEAR, GPSR, GAF等算法没有对多路径进行充分考虑, 而以数据为中心的路由协议SPIN, LEACH, TEEN等算法是通过分簇选择簇首传递数据而达到延长网络生存时间的目的。上述路由协议都是为快速地在各个节点之间建立最短路径, 转发数据较多节点的电量会消耗过快, 存在着单点故障的可能, 因此降低网络的可用性以及存活时间, 对于可用性、实时性需求较高的工业无线网络环境, 这些路由协议不能较好地自适应。
3 多路径路由算法
在工业无线网络中, 网关节点和路由节点的位置已经相对固定, 故多使用静态路由, 具体的路由策略是由网络管理者配置的, 在WIA-PA规范定义中, 每个设备都具有唯一的64位物理地址和一个16位的网络层短地址。终端设备传递数据时, 直接将数据传送给所连接的路由设备, 路由设备则通过目的地址来决定如何进行传输:如果目的地址为网关地址, 则直接传输给网关;如果是簇地址, 则把数据传送给目的簇所对应的路由设备。
3.1 网络模型
WIA-PA规范里所定义的网络模型中, 整个网络建立过程如下, 待加入网络的路由设备侦听由网关的信标, 如果待加入网络的路由设备收到网关的信标, 则向网关发送加入请求, 通过相应的验证之后, 加入网络;如果待加入网络的路由设备收到的是已经加入网络其他路由设备发出的信标, 发送加入请求, 通过验证后加入网络, 然后由路由设备向网络管理者提交更新之后的网络邻居信息。网络管理者由邻居信息表可以得到整个网络的拓扑图。路由设备通过接收到信标的网关或者路由设备加入网络, 但它的位置并不能直接由上游的接入设备来确定考虑节点。
3.2 算法描述
在网络建立好之后, 通过各个节点发送路由泛洪包, 来寻找多路径, 泛洪包的格式协议仿真与性能分析本文使用OMNET++仿真平台对设计的多路径算法进行仿真实验, 对于仿真实验的物理层协议和MAC协议均采用IEEE 802.15.4标准, 仿真时间设置600s, 布置区域800m×600m, 信道2.4 GHz, 带宽250kb/s, 信道错误率0.01%, 射频辐射范围200m。仿真结果显示, 通过使用该算法, 节点在进行数据转发时, 会优先选择有源节点或电量相对充足的节点, 各节点的电量消耗较为平均, 提高了整个网络的生存时间。在端到端延时方面, 运行该算法的节点在传送数据时, 依靠节点自身的电量信息及链路状态来选择下一跳节点, 而现行的一些单路径算法在节点失效时需重新选择路径, 算法运行时间上的差异不大, 不会引起网络端到端延时增大。能量消耗随着干扰强度的增加, 扩展LEACH机制的网络能量开销降低, 逐跳多径机制的网络能量消耗加快, 而节能多径机制的能量消耗增幅较小, 这是因为随着干扰强度增加, 泛洪机制和扩展LEACH机制网络中的转发报文数量减少, 所以能量开销会降低;而对于逐跳单径和节能多径机制, 不仅不会因为干扰导致丢包使得网络中的报文数量减少, 反而会因为备用多径的重新转发报文带来更多的能量开销。
结束语
由于工业无线监测网络的工作环境具有多样性, 因此, 未来的一个重要任务就是提高可用性和抗干扰能力, 克服外界环境变化造成的影响。单路径路由转发数据不但会引起节点电量消耗过快, 并且在环境干扰较大的工业环境中数据传输的可靠性也大大降低。通过采用多路径路由算法, 传输数据时依据节点电量消耗比率来选择优先传输路径, 解决了单一节点转发数据较多引起的能量消耗过快, 网络存活时间低的问题。此外, 改善了单路径中单一节点电量消耗过快问题, 使得各个节点的电量消耗较为均衡, 提高了网络的可靠性和可用性, 从而延长网络存活时间。由于算法使用泛洪的方式来寻找多条路径, 因此, 网络中大量节点受到干扰时, 路由的收敛时间将受到泛洪时间间隔的影响, 快速收敛会变慢, 而对实时性要求较高、大规模的工业无线网络, 多路径路由的快速收敛问题也是今后研究工作的重点。
摘要：网络路由一直是网络的关键问题, 今天的计算机网络非常庞大、高速, 传载着各种多媒体信息, 因此, 网络路由面临新的挑战。本文通过分析工业无线网络环境中网络拓扑结构的特点, 设计了一种适用于工业过程自动化无线网络规范的多路径路由。根据WIAPA网络拓扑稳定、工作环境干扰较大的特点, 通过采用多路径数据传输, 解决了单一节点转发数据较多引起的能量消耗过快、网络存活时间低的问题。
关键词：工业无线网络,多路径路由,路径选择,节能
参考文献
[1]孙利民, 李建中, 陈渝.无线传感器网络[M].北京:清华大学出版社, 2005.[1]孙利民, 李建中, 陈渝.无线传感器网络[M].北京:清华大学出版社, 2005.
[2]张宏科, 张思东, 刘文红.路由器原理与技术[M].北京:国防工业出版社, 2002:70-178.[2]张宏科, 张思东, 刘文红.路由器原理与技术[M].北京:国防工业出版社, 2002:70-178.
路由器的构造及路由算法的研究 篇4
关键词：网络时代,路由器构造,路由算法
1 路由器的构造
路由器是组建互联网的重要设备，路由器和PC机非常相似，有硬件部分和软件部分组成，只不过它没有键盘、鼠标、显示器等外设。IOS是路由器的操作系统，是它的软件组成。路由器是第三层设备，通过运行路由协议了解整个网络的路由情况，并建立一个指示路径的路由表。当用户数据进入路由器后，路由器根据接收到的数据包包头中的第三层地址信息，查阅路由表，把数据从一个接口交换到另一个接口。
1.1 中央处理器（CPU)
和计算机一样，路由器也包含中央处理器。路由器的处理器负责许多预算工作，比如维护路由所需的各种表项以及做出路由选择等。路由器处理数据包的速度在很大程度上取决于处理器的类型。某些高端的路由器上会拥有很多个CPU并行工作。
1.2 内存
在路由器中，主要有以下几个类型的内存：1)只读内存(ROM);2)随即访问内存(RAM);3)闪存(FLASH);4)非易失性内存 (NVRAM) 。
1.3 接口（Interface)
路由器的接口是配置路由器的主要考虑对象之一，同一台路由器上不同接口的地址应属于不同的网络。路由器通过接口在物理上把处于不同逻辑地址的网络连接起来。这些网络的类型可以相同，也可以不同。路由器的一些接口是ISDN接口、串行接口，它们通常将路由器连接到广域网链路上;还有一些是局域网接口(LAN接口)，例如Ethe rne t、令牌环网和FDDI等。
1.4 路由器的软件
如PC机一样，路由器也需要操作系统才能运行。路由器的操作系统叫做IOS (InternetworkOperating System)。路由器平台不同、功能不同，运行的IOS也不尽相同。
2 路由器算法
2.1 硬件算法
目前使用最多的硬件实现方法是使用CAM (Content Addressable Me m ory)内容可寻址存储器，它是一种特殊的存储器件，用来实现路由表查找的一种硬件方法。CAM的最大特点是能够在一个硬件时钟周期内完成关键字的精确匹配查找。为了能够实现最长前缀匹配，一个CAM表存放一类定长的前缀集。IPV4下需要32个CAM。这种方法有一个明显的缺点，在对地址前缀长度具体分配没有准确的了解之前，为了能够保证存储N个前缀表项目，每个CAM都要有N个表项的空间，因此，CAM存储空间的利用率大大降低了。
另一种基于硬件的改进CAM算法是基于TCAM(三值CAM)的算法。在进行搜索的时候，所有的TCAM项都需要同时进行匹配，在有多个匹配项时，TCAM规定在所有匹配的表项中选取地址最低的表项作为最后的结果。因此，为了能够进行最长前缀路由的查找，就需要保证在TCAM的低地址区域存储前缀路由项，而在高地址区域存储短前缀路由项。TCAM具有速度快、实现简单的优点，但它也具有几个不足之处：1)单位比特昂贵;2)容量小;3)并行匹配导致功耗很大;4)更新复杂。
2.2 软件算法
IP路由要求查找最长匹配的前缀地址，因此树形结构的路由查找算法将最长前缀匹配查找模型话为一棵二进制树的过程。用Trie表示前缀并不存储在Trie的结点中，而是用结点间的路径表示前缀，一般规定一个结点到其左子结点的路径表示前缀中的对应比特为0，结点到其右子结点的路径代表前缀中的对应比特为1。IPv4中地址长度为32，所以二进制trie树的深度为32层，前缀长度即子网掩码长度为L的网络路由会被存放在第L层的结点中。二进制trie树算法一次更新操作只需要首先查询定位并修改一个结点，开销较小，它的最大不足在于查找过程中要进行大量的存储访问，对于IPv4地址查找最多需要32次，IPv6地址为128次。
节能路由算法 篇5
无线传感器网络WSN由一组传感器节点以自组织方式构成。每个节点兼备路由器和主机两种功能,不仅要执行感知、传输数据等应用任务,还要参与路由发现、维护以及网络构建等任务。WSN中节点一般采用电池供电,节点大部分情况下被布置在无人看守的环境中,电池不能补充和更换,节点能量受限。在这种情况下要延长网络生存时间就必须降低节点工作时能量消耗,试验表明节点能量主要消耗在通信模块上。无线通信中的传输数据的能量消耗与有效半径的2-4次方相关,减小节点的有效传输半径可以降低节点能量消耗。
另外WSN还有着不同于传统无线网络的其他特征:首先WSN中节点数量庞大,传统的以IP地址为基础的路由协议不适合WSN;其次WSN的应用背景主要是多个源节点感知数据,然后将感知数据传给目的节点Sink,不要求建立网络中任意两点之间的路由路径,这给设计高效的路由协议带来了可能性。因此采用合适的、高效的路由协议是降低无线传感器网络整体能耗的关键。这就需要我们设计一个满足需要的高效的路由协议。
1 相关工作
研究工作者们提出了许多的路由算法,比如SPIN[1](基于协商的路由算法)、DD[2](定向扩散协议)、LEACH[3]、TTDD[4](基于虚拟网格的路由协议)、LAR[5](位置辅助路由协议)等路由协议。他们都很好地解决了无线传感器网络的某方面的问题,但也都存在各自的问题。比如SPIN协议中出现了多个节点向同一个节点同时发送REQ的情况,有关的退避机制需要考虑。DD算法不能用于大规模的网络,主要用于具有大量查询而只有少量事件的应用场景,如果网络拓扑结构频繁变动,它的性能将大幅下降。
在WSN中,从源节点到基站或是到基站的某条传输路径一旦确定,就不会频繁改动,这样就会出现由于路径上的传输节点的失效或暂时不可用导致数据包传输失败,为此需要重新更新路由,增大了能耗和传输延迟。为了解决这个问题,研究工作者们提出了多路径路由[6,7]的概念。多路径路由协议通过将数据流分散到多个不同的路径上传送以实现负载的均衡性,在WSN中体现为能量的均衡性,并且可以通过增加冗余路径来提高网络的可靠性。优化增加了网络的可靠性,但同时也增加了网络能耗。
混合蛙跳算法[8]可以实现路由优化的目的,但是传统的混合蛙跳算法不能将可行解中的优良性能很好地保留在青蛙群体中,它的收敛速度也比较慢,这就表明了传统的混合蛙跳算法不适用于能量有限的无线传感器网络中。
针对以上问题,我们提出了一种改进的混合蛙跳算法来全局优化多路径路由。考虑到混合蛙跳算法的计算量大,所需要的资源信息较多,我们将混合蛙跳算法的执行在基站完成。这样就解决了由于建立多路径导致的网络能量浪费,又实现了多路径路由的优点,实现了WSN多路径路由的全局优化。
2 WSN路由优化算法
混合蛙跳算法是一种基于群体智能的生物进化算法。在WSN中,青蛙群体由一群具有相同结构的青蛙组成。整个群体被分为多个族群,每个族群有自己的思想,执行局部优化策略。在局部优化迭代结束后,各个族群之间进行思想交流,实现族群间的混合运算。达到了路由优化的目的。
2.1 网络模型
WSN网络模型假设如下:
1) 所有节点随机均匀地分布在一矩形区域内。且位置已知。
2) 所有节点与基站均保持静止,节点初始能量相同,并无法补充能量。基站的能量无限大。
3) 所有节点均同构,且唯一ID,并具有数据融合功能。
4) 每个节点的传输功率相同,有效通信距离均一样。
将无线传感器网络模型表示为一个有向图G=(V,E),其中V表示所有节点的集合,E表示所有边的集合。令r为节点v∈V的发射范围,L表示相邻节点间的距离。随机生成F只青蛙组成初始群体,每个青蛙个体表示一条源节点到基点的可行路径为U = (U1,U2 ,…,Ud),其中d表示解空间的维数。例如5个传感器节点组成的网络链路如图1所示。
随机生成的初始群体:
U1={S,1,2,BS} U2={S,1,3,2,BS}
U3={S,1,2,4,BS} U4={S,3,2,BS}
U5={S,1,2,3,4,BS} U6={S,4,BS}
U7={S,3,2,4,BS} U8={S,3,1,2,BS}
U9={S,3,4,BS} U10={S,4,3,2,BS}
2.2 算法描述
路由协议的好坏极大地影响整个网络的性能。好的路由协议不仅能够降低整个网络的能量消耗,延长网络生存周期,还能提高网络的稳定性。基于混合蛙跳算法的多路径路由的优化主要考虑了传输数据的能耗和可靠性两方面来全局优化多路径路由。以下为优化算法的具体步骤:
1) 初始化参数
在无线传感器网络中,按一定规则随机生成F只青蛙组成初始群体,计算青蛙个体的适应度f(i)。青蛙个体的适应度函数定义为:
其中D(u,x)表示源节点u在链路(u,x)上分配的数据流量,g(x,u)表示节点u在链路(x,u)上接收单位数据所消耗的能量,R(x,u)表示节点u在链路(x,u)上接收到的数据流量,t(u,x)表示节点u在链路(u,x)上发送单位数据所消耗的能量,W(u)表示感知的数据量。
2) 构造子族群
将生成的青蛙按适应度降序排列划分成m个族群,构造子族群。在随机生成初始群体之后,将青蛙个体按适应度f(i)降序排列存储于X={Ui},i=1,2,…,F,然后按照以下划分原则将整个青蛙群体分成m个族群Y1,Y2,…,Ym,每个族群中包含n只青蛙,满足下列关系:
Yij=X[j+(i-1)×n] i=1,2,…,m j=1,2,…,n
假设m=3,F只青蛙按适应度由高到低排列,位置位于第1 的青蛙分入第1 族群,第2 的青蛙分入第2 族群,第3 的青蛙分入第3 族群,第4的青蛙分入第1 族群,依次类推,将所有青蛙个体划分到3 个族群中。
3) 局部优化
将青蛙种群划分的多个族群进行局部优化。在每一个子族群中,具有最好适应度的可行路径表示为Ub,最差适应度的可行路径表示为Uw 。对每个子族群的局部优化,主要是对Ub和Uw进行交叉替换操作。具体的操作可如下进行:
(1) 在Ub和Uw中查找它们的公共基因,即查看两条路径是否同时经过某个节点,如果存在公共基因表明可以进行交叉。如果没有,则表明这两个个体不能交叉。
(2) 从选中的这个公共基因开始,直到下一个公共基因 (如果两条路径仅有一个相同节点,则取目的节点为下一个公共节点) ,对Uw进行链路交换。
例如: Ub={S,1,3,4, BS}
Uw={S,1,2,4,BS}
节点1、节点4为公共节点,经过交叉后,Ub不变。Uw变为:
Uw={S,1,3,4,BS}
计算交叉后的最差青蛙的适应度f′(w),如果f′(w)大于交叉前最差青蛙的适应度f(w),则交叉成功,否则交叉失败。如果交叉失败,再选用全局最优青蛙与最差青蛙进行交叉替换。交叉后判断交叉前后的最差青蛙的适应度,如果f′(w)大于f(w),则交叉完成,否则随机产生一个新的青蛙代替原来的最差的青蛙,交叉结束。
(3) 交叉后再对子族群中的所有的青蛙进行变异。每一个青蛙都以固定的概率p进行变异,大量实验表明p的值取0.02比较理想。子族群中的最优青蛙Ub也可能变异,为了防止变异后的Ub变得比原来的适应度差,如果变异后的Ub的适应度f′(b)大于变异前的适应度f(b),则发生变异,否则不进行变异。
4) 全局优化
所有子族群经过一定次数的局部优化后,将所有族群的青蛙混合在一起,重新计算适应度f(i),按适应度f(i)降序排列,重新划分族群,再进行局部优化,如此循环直到满足收敛条件为止。
2.3 算法分析
随机生成青蛙种群的时候,在可行路径中的节点的选择时,加入了节点的剩余能量的考虑。剩余能量越大的节点被选中的概率越大。概率q=E1/E2,E1表示节点的剩余能量,E2表示节点的初始能量。剩余能量的考虑缓解了部分节点因大量使用而死亡的问题。
改进的混合蛙跳算法改进了子族群青蛙局部优化方法,主要是对子族群中青蛙进行交叉变异操作,对子族群中最优青蛙和最差青蛙的交叉操作,考虑了多种情况,避免了局部早熟。随后进行概率变异操作,变异中如果最优的青蛙如果发生变异,要进行比对。这样不仅保证了青蛙个体的多样性,而且保留了青蛙的优良性,缩短了找到全局最优解的时间。
在每次的优化后保存最优的青蛙和次优的青蛙。采用这样的多路径路由可获得比单路路由更好的网络吞吐率和可伸缩性。如果最优路径中的某一个或几个节点的剩余能量很低,并且下一轮的路由更新还没开始,最优路径就不能传输数据。多路径路由就可以只使用次优的路径进行传输,保证了网络的流通,增加了网络的可靠性。
3 算法实现和实验仿真
3.1 算法流程
1) 基站收集网络初始信息。得到网络各个节点的邻居矩阵N和感知数据集合{W(u)|u∈V}。
2) 对网络节点ID编码并初始化青蛙群体。
3) 依据青蛙适应度划分生成青蛙种群。
4) 针对子族群中最优青蛙和最差青蛙进行选择替换操作,然后子群青蛙按概率0.02进行变异。
5) 混合子族群,再重复3)、4)操作;直到满足收敛条件为止。
6) 输出青蛙种群中适应度最优和次优的青蛙作为问题的满意解。
3.2 实验仿真
在下面的实验中,通过仿真网络中节点的通信和节点的能量消耗,主要从网络能量消耗方面进行了实验分析。
基本参数设定
网络的负荷根据控制系统的一般要求设置为:周期性发送和感知数据,各节点的发送数据周期为0.01 s～0.10 s,感知数据周期为0.1 s～0.5 s。青蛙更新迭代次数IT=10。定义网络生存周期为网络从运行开始到网络中死亡节点的百分数低于原来总节点数的50%时所持续的时间。
选择经典的传感网络路由算法定向扩散(DD) 算法作为比较对象。在同一环境下分别对混合蛙跳算法和DD算法的网络生存周期进行仿真测试。仿真结果如图2所示。
从图2中可以看出,采用改进的混合蛙跳算法的WSN路由优化算法具有更长的网络生存周期,并且随着感知数据量的增大,网络生存周期延长的效果越明显。说明混合蛙跳算法对于大数据量的全局优化更加突出。
4 结 语
本文在分析了现有的混合蛙跳算法的基础上,结合无线传感器网络的特点,提出了一种适合于无线传感器网络的路由优化算法。改进的混合蛙跳路由优化算法考虑到了节点的剩余能量,并且复杂的优化计算问题由能源充足、计算和存储能力强大的基站解决,平衡了节点能量负载,节省了能量消耗。仿真实验表明,相比DD算法,新算法均衡了网络能量消耗,有效地提高了网络生存周期,改善了网络性能。
参考文献
[1]WHeinzelman,J Kulik,HBalakrishnan.Adaptive Protocols for Infor-mation Dissemination in Wireless Sensor Networks[C]//Proc.5thACM/IEEE Mobicom,Seattle,WA,Aug 1999:174-85.
[2]C Intanagonwiwat,R Govindan,D Estrin.Directed Diffusion:a Scala-ble and Robust Communication Paradigm for Sensor Networks[C]//Proc.ACMMobi-Com2000,Boston,MA,2000:56-57.
[3]Heinzelman W,Chandrakasan A,Balakrishman H.Energy efficientcommunication protocol for wireless microsensor networks[C]//Proc ofthe 33rd Hawaii International Conference on Systern Sciences.Maui:IEEE Computer.
[4]HLuo,Fan YE,J Cheng,et al.TTDD:A Two-tier Data DisseminationModel for Largescale Wireless Sensor Networks[J].Wireless Net-works,2005,11(2):161-175.
[5]Young-Bae Ko,Nitin H Vaidya.Location-Aided Routing(LAR)inmobile ad hoc networks[J].ACM/Baltzer Wireless Networks(WI-NET)Journal,2000,6(4):307-321.
[6]Lees J,Gerlam.Sp litmultipath routing with maximally disjoint paths inAd Hoc networks[EB/OL].[2008-06-18].http://www.hp l.hp.com/personal/Sung-Ju_Lee/abstracts/papers/icc2001b.pdf.
[7]周集良,李彩霞,曹奇英.基于遗传算法的WSNs多路径路由优化[J].计算机应用,2009(2):521-524.
ZigBee路由算法的改进 篇6
近年来, 作为在低速率的无线传感器网络和控制网络中最受瞩目的技术之一, Zig Bee以其低成本、低功耗、低速率、高可靠性等特性, 广泛应用于工业、医疗、军事、智能家居等需要低功耗、低成本, 对数据传输速率和服务质量要求不高的无线通信应用场合[1]。
Zig Bee网络层 (NWK) 介于MAC层和应用层之间, 是由Zig Bee联盟制定的。Zig Bee网络层的主要功能就是确保Zig Bee的MAC层能正常工作, 并且提供适合的服务接口给应用层。网络层提供了两个必要的功能服务实体用于向应用层提供接口:数据服务实体和管理服务实体[1,2]。
NWK主要功能有: (1) 加入和离开网络; (2) 帧的安全机制管理; (3) 根据路由发送帧到目的地址; (4) 发现和维护路由; (5) 发现单跳邻居节点和维护邻居节点信息。
二、Zig Bee网络层技术简介
2.1 网络拓扑结构及地址分配
Zig Bee网络中存在三种网络节点, 分别为中心协调器、路由节点和终端节点。协调器是整个Zig Bee网络的中心, 是协调点, 负责整个网络的组织、维护和管理工作, 必须由FFD (全功能设备) 构成;路由节点负责数据的传输和转发功能, 必须由FFD构成, 但路由节点必须由协调器控制;终端节点负责自身数据的发送并接收其他节点传过来的数据, 可以由FFD或RFD (精简功能设备) 构成。
Zig Bee网络有星型、网状型和树型三种拓扑组织形式。由于树型网络结合了星型结构和网状结构的优点, 且具有较好的扩展性, 所以Zig Bee网络一般采用簇树拓扑结构组织节点。中心协调器启动后就创建一个网络, 设置自身网络地址为0, 路由节点和终端节点选择相应的有路由功能的父节点加入网络, 形成父子关系。成功加入网络后, 该节点获得父节点分配的一个唯一的网络地址。
规定每个父节点最多可以连接Cm个子节点, 这些子节点中最多可以有Rm个路由节点, 网络的最大深度为Lm, Cskip (d) 是网络深度为d的父节点为其子节点分配的地址之间的偏移量, 它的值按公式 (1) 计算, 分配给第k个子路由节点的地址Ak满足式 (2) , 分配给第n个子路由器节点的地址Ak满足式 (3) 。其中, Afather代表父节点的地址。
2.2 Cluster-tree路由算法
Cluster-tree算法根据树结构转发分组, 如果终端节点要发送数据包到网络中的其他节点, 则直接将该数据包转发给其父节点, 由父节点进行转发。
如果一个路由器节点要转发数据包到网络地址为D的目的节点, 已知该路由器节点的网络地址和深度分别为A和d。
首先, 该路由器节点会依据下述表达式判断目的节点是否是其后裔节点:
如果目的节点是其后裔节点, 则下一跳节点地址为:
否则, 如果目的节点不是其后裔节点, 则下一跳节点为该节点的父节点。
2.3 AODVjr路由算法
AODVjr[3]是AODV的简化版本, 具有AODV的主要功能, 但考虑到降低成本、节能、使用的方便性等因素, 简化了AODV的一些特点。
首先AODVjr舍弃了AODV中的目的节点序列号, 为保证路由无环路, AODVjr中规定只有分组的目的节点可以对RREQ (路由请求) 分组进行响应, 即使中间节点存在通往目的节点的路由也不能回复。同时AODVjr不存在AODV中的“先驱节点列表”, 从而简化了路由表结构。另外AODVjr取消了HELLO信息的发送, 由目标节点定期向源节点发送KEEP_ALIVE连接信息来维持路由[4,5,6]。
三、改进的算法设计
3.1 问题的提出
Cluster-tree算法不存在路由发现过程, 限制了寻址的灵活性, 建立的路由不一定是最优的, 从而浪费网络能耗并且引入服务延迟。因而, Zig Bee中允许有路由能力的节点使用AODVjr去发现一条最优路由。但是AODVjr算法在路由发现过程中会产生多余的RREQ分组, 容易引起广播风暴。例如, 图1中节点1发起路由发现, 寻找到节点7的路径, 节点1向所有邻居节点发送RREQ分组, 而向节点1的后裔节点2和3发送RREQ分组对寻找路由帮助不大, 成为多余的RREQ分组。同理节点7要寻找到节点9的路径, 向其父节点0广播也将产生多余的RREQ分组。
此外, 由于网络中某些节点传输数据量过大, 特别是距离中心协调器越近的节点, 从而提前耗尽自身能量, 容易造成网络分割, 影响了整个网络的通信, 缩短了网络的寿命。
针对以上问题, 本文从控制RREQ分组以及能量均衡的角度出发, 提出一种改进的算法, 有效的限制AOD-Vjr路由发现过程中的RREQ的广播, 延迟网络分割出现的时间, 从而提高网络的性能。
3.2 改进的路由算法M_ZBR
3.2.1 冗余RREQ分组的控制
改进的路由算法M_ZBR在路由发现阶段, 利用Cluster-tree结构及算法的特点, 根据公式 (4) 判断出目的节点与当前节点的关系, 从而判断出RREQ分组转发最佳的大致方向。因此, M_ZBR算法在RREQ分组中增加一个标志位flag。当目的节点为当前节点的后裔节点时, flag=0, 即表示当前节点的父节点不宜转发该RREQ分组;当目的节点不是当前节点的后裔节点时, flag=1, 即表示当前节点的后裔节点不宜转发该RREQ分组。
另外, 从树结构可以看出, 若在使用Cluster-tree路由算法时, 可能存在的最长路径应是网络最大深度的2倍。由此, M_ZBR算法通过设定最大传输跳数也可以减少部分冗余的RREQ分组, 本算法中, 当跳数hops>2Lm时, 节点便丢弃该RREQ分组。
3.2.2 节点能量的控制
M_ZBR算法根据Zig Bee路由算法的特点, 对Zig Bee网络中的路由节点采用了能量控制机制, 这对延长网络寿命, 延迟死亡节点以及网络分割出现的时间都是十分必要的。因此, M_ZBR算法定义了节点最小路由能量Emin, 当节点的能量低于Emin时, 路由节点将不再发起路由发现, 即不再采用AODVjr路由算法。
在Zig Bee网络中, 越靠近中心协调器的节点参与数据传输就越频繁, 对整个网络的通信来说也就越重要, 所以Emin的能量控制应与节点深度成反比, 深度越小节点应具有相对较大的最小路由能量, 因此, 将Emin定义为:
其中, Elimit为节点正常工作需要的最小能量值, 为控制系数, 可以根据需要人为的控制Emin的大小, d为节点的深度。
此外, M_ZBR算法依据节点最小路由能量的定义, 设置一个节点能量警戒值Ewarning:
其中, k为大于1的控制系数。
依据以上节点能量阈值的设置, M_ZBR算法在RREQ分组中增加了能量标志位energy_flag, 用于统计RREQ分组传输过程中统计处于能量警戒区内的节点个数。
3.2.3 算法流程
(1) 当RFD节点要给网络中其他节点发送数据时, 直接采用Cluster-tree算法, 即将数据转发给其父节点, 由其父节点转发。 (2) 当FFD节点要发送数据到网络中其他节点时, 首先查找路由表中有无到目的节点的路由表项, 若有则按路由表转发数据包, 若无则启动路由发现过程。 (3) 在路由发现阶段, 任意节点收到RREQ分组时, 首先检测本节点是不是该RREQ分组的目的节点, 如果不是, 则转 (4) ;若是, 则转 (9) 。 (4) 判断节点自身的剩余能量, 如果剩余能量小于节点最小路由能量Emin则直接丢弃RREQ分组, 否则转 (5) 。 (5) 查看RREQ分组中的跳数值, 若hops>2Lm, 则丢弃RREQ分组, 否则转 (6) 。 (6) 查看RREQ分组中的标志位flag, 若flag=0, 转 (7) , 若flag=1, 则转 (8) 。 (7) flag=0表明本节点不宜转发子节点发送的分组, 需判断本节点是否为前一跳的父节点, 若是, 则丢弃RREQ分组;若不是, 则判断目的节点是否为当前节点的后裔节点, 如果是, flag的值继续为0, 直接转发分组, 若目的节点是当前节点的后裔节点, 则设置flag=1。 (8) flag=1表明本节点不宜转发父节点发送的分组, 需判断本节点是否为前一跳的子节点, 若是, 则丢弃该分组;若不是, 则需判断目的节点是否为当前节点后裔节点, 如果是, 则设置flag=0, 若目的节点不是当前节点的后裔节点, flag的值继续为1, 直接转发分组。 (9) 当目的节点收到RREQ分组时, 判断自身剩余能量, 若小于Emin, 直接回复RREP;否则将收到的分组放入缓存区, 在缓存时间t内, 比较各RREQ分组的能量标志位energy_flag, 选择energy_flag最小的RREQ分组且回复RREP。
四、仿真结果分析
为了验证改进算法的实际效果, 通过仿真实验对比原来的AODVjr算法, 分别比较了死亡节点个数以及总能量损耗, 仿真结果证明了算法的可行性和有效性。
图3是原AODVjr算法与改进算法死亡节点数的比较, 曲线 (1) 是原AODVjr算法随数据流量增加而变化的死亡节点数, 曲线 (2) 是改进后的算法的死亡节点数。当数据流量较小时, 节点能耗就较少, 节点死亡数相对就比较少。当数据流量增加时, 死亡节点数也会增加, 改进的算法通过能量标志位的判断, 选取能量标志位最小的RREQ分组并回复, 明显比原算法的死亡节点数增加的缓慢。
图4比较了改进算法与原算法的网络总能量耗损。曲线 (1) 是原AODVjr算法随数据流量增加而变化的网络总能量耗损, 曲线 (2) 是改进后的算法的网络总能量耗损。显然, 改进的AODVjr算法通过控制了RREQ分组减少了网络的耗能。
五、结论
本文主要针对Zig Bee的路由协议进行分析, 基于能量均衡对Zig Bee现有的路由算法AODVjr提出了改进, 通过限制路由发现过程中的RREQ的广播, 很好的延迟网络分割出现的时间, 从而提高网络的性能。仿真实验将原算法和改进的算法进行了比较, 改进的路由算法有效地减少了总耗能与死亡节点数。
摘要：网络层的路由协议是ZigBee协议规范的研究重点之一, 因为网络节点中节点的能量资源、计算能力和带宽都非常有限, 路由算法优化与否对整个网络的性能有着至关重要的作用。从控制RREQ分组以及能量均衡的角度出发, 对AODVjr算法提出了改进。通过仿真实验, 将改进的算法与原AODVjr算法进行性能参数的比较分析, 实验结果验证了改进后的算法的有效性。
关键词：ZigBee,路由算法,AODVjr,无线传感器网络
参考文献
[1]ZigBee Alliance.ZigBee Document053474r13[S].December1, 2006.
[2]朱向庆, 王建明.ZigBee协议网络层的研究与实现.电子技术应用.2006.1:129
[3]Hakeres I D, KleinBerodt.AODVjr, AODVsimplified[J].Mobile Computingand Communication Review, 2002, 6 (3) :100-101.
[4]班艳丽, 柴乔林, 王芳.改进的ZigBee网络路由算法.计算机工程与应用, 2009, 45 (5) :95-97
[4]谢川.基于ZigBee的AODVjr算法研究.计算机工程, 2011, 37 (10) :87-89
路由查找算法研究与分析 篇7
当前，因特网的规模、链路速度、带宽、流量等都呈指数级增长，这对路由器中IP路由查找算法对大容量路由表处理的适应性以及报文转发查表的能力提出了更高要求。路由器是构成因特网的中间结点，其转发性能决定了因特网的整体性能。路由器的发展面临三个难题：交换结构、缓冲调度、报文处理。随着半导体技术和光交换技术的发展，分组交换可以在很高的速率下得到实现。因此，IP路由查找是实现高速分组转发的关键，其优劣直接影响了当前和未来因特网网络的整体性能[1]。本文首先对现有的典型IP路由算法进行介绍，总结其优缺点，并基于此提出一种基于多分枝trie树的路由查找算法。
2 常用的路由查找算法分析
2.1 硬件算法
目前使用最多的硬件实现方法是使用CAM (Content AddressableMemory) 内容可寻址存储器[2]，它是一种特殊的存储器件，用来实现路由表查找的一种硬件方法。CAM的最大特点是能够在一个硬件时钟周期内完成关键字的精确匹配查找。为了能够实现最长前缀匹配，一个CAM表存放一类定长的前缀集。IPV4下需要32个CAM。这种方法有一个明显的缺点，在对地址前缀长度具体分配没有准确的了解之前，为了能够保证存储N个前缀表项目，每个CAM都要有N个表项的空间，因此，CAM存储空间的利用率大大降低了。
另一种基于硬件的改进CAM算法是基于TCAM (三值CAM) 的算法[3]。在进行搜索的时候，所有的TCAM项都需要同时进行匹配，在有多个匹配项时，TCAM规定在所有匹配的表项中选取地址最低的表项作为最后的结果。因此，为了能够进行最长前缀路由的查找，就需要保证在TCAM的低地址区域存储前缀路由项，而在高地址区域存储短前缀路由项。TCAM具有速度快、实现简单的优点，但它也具有几个不足之处： (1) 单位比特昂贵; (2) 容量小; (3) 并行匹配导致功耗很大; (4) 更新复杂。
2.2 软件算法
2.2.1 二进制trie树[4]
IP路由要求查找最长匹配的前缀地址，因此树形结构的路由查找算法将最长前缀匹配查找模型话为一棵二进制树的过程。用Trie表示前缀并不存储在Trie的结点中，而是用结点间的路径表示前缀，一般规定一个结点到其左子结点的路径表示前缀中的对应比特为0，结点到其右子结点的路径代表前缀中的对应比特为1。如图1所示就是二进制trie树结构来表示的地址前缀结构。
IPv4中地址长度为32，所以二进制trie树的深度为32层，前缀长度即子网掩码长度为L的网络路由会被存放在第L层的结点中。二进制trie树算法一次更新操作只需要首先查询定位并修改一个结点，开销较小，它的最大不足在于查找过程中要进行大量的存储访问，对于IPv4地址查找最多需要32次，IPv6地址为128次。
2.2.2 多分支trie树
直接用二进制trie树的方式来实现路由查找，查找一个比特即对二叉树向下遍历一个深度，这样会导致查找速度太慢。如果一次从目的IP中取出多个比特，就可以开有效的减少查找过程中的存储访问次数。多分支trie树的查找过程与二进制trie树的查找过程类似，在每次结点访问过程时，记录下到目前为止匹配上的最长地址前缀，直到到达叶子结点搜索过程结束。例如，如果每次检查地址的4个比特，那么IPv4地址查找最多只需要8次存储访问就可以了。图2是和前面图1中采用同样IP前缀表生成的多分支trie树结构图。
每次从目的IP中取出的比特长度K称为查找步长。由于存储树中的前缀长度各不相同，如果每次检查步长为K的比特数，则小于K或者不是K整数倍的前缀将无法与多分支trie树的某个结点匹配。解决的方法是将无法匹配的前缀扩展为同K相同或者和K的整数倍。例如，K=3时，可以将1*扩展为100*、101*、110*、和111*。这种采用扩展前缀进行查找多分支trie树的算法称为可控前缀扩展算法。
当然，这种地址前缀扩展的多分支trie树在减少访存次数的同时也带来了消耗存储空间增大以及更新复杂的问题。假设步长K=5，那么就有4/5的IP前缀需要扩展(假设IP前缀长度均匀分布)，最大的扩展长度前缀都要进行扩展到24个，这样就消耗了大量的存储空间。此时要更新某个IP前缀，最多需要更新24个结点。
文献[5]中列举了多分支trie树算法取不同步长时的实际运行性能比较。当步长K较大时，多分支trie树的深度相对较小，因此查找性能较好，但是需要耗费较多的存储空间。当步长K较小时，多分支trie树的深度相对较大，查找性能较差，但是存储空间需求较小。可见，对于多分支trie树来说，查找速度和存储容量是一对互相矛盾的性能指标。
3 路由查找算法的衡量标准及性能提高方法
在评价一种地址查找算法的优劣时，必须综合考虑以下性能[6]：
3.1 查找速度。
一般所使用的指标是每秒查找分组数。考虑到各种方案在测试时所使用硬件不同、测试条件的不同会对测试结果产生很大影响，所以使用一次查找、特别是最差情况下一次查找需要进行的存储器访问次数作为衡量速度的标准更为合理。
3.2 所需存储器的大小。
实施方案所需的存储器应尽可能的小，在一定的空间中存储尽可能多的路由前缀，以便于硬件实现和满足不断增长的前缀数目的需要。
3.3 路由表更新的开销。
包括路由表周期更新开销和表项插入、删除操作开销两部分。路由信息的变化所引起的查找性能的下降应尽可能的小。
提高路由查找速度的主要途径有3个[7]：(1)减少存储器访问次数;(2)减小转发表的存储空间;(3)采用硬件流水并行处理。只采用一种方法或者算法所得到的查找性能受到一定的限制，既使能够取得很快的查找速度，往往也存在转发表更新困难或者扩展性差等问题。所以很多算法都是把这3个方向上的改进结合起来的结果。
4 一种改进的多分支trie树算法
我们提出一种多分支trie树改进算法。在多分支trie树结构基础上，不需要进行前缀扩展。假设检查步长为K的比特数，为解决小于K或者不是K整数倍的前缀将无法与多分支trie树的某个结点匹配问题，把小于K或者不是K整数倍的前缀挂载到K的整数倍结点上，以整数倍结点为根结点，组成一个大的中间结点。即，中间结点之间采用多分支步长查询，中间结点的内部使用二进制trie树来表示。
图3列举了步长K=3时，某个中间结点的表示方法。前缀100110是K的整数倍结点，即中间结点。1001100, 1001101, 10011010都不是K的整数倍结点，把他们挂载在100110的中间结点上。图4是使用前面的IP前缀表生成的结构图。
在路由查询时，使用步长为K访问中间结点，找到中间结点后，以步长为1访问中间结点内部。一个长度为N的前缀，所需要的访存次数为N/K的结果加上N/K的余数。以步长K为3为例，假设前缀长度N为11，那么访存次数为3+2=5次。最坏情况下，IPv4地址前缀最长为32，访存次数为10+2=12次，仅比原来的多分支trie树的10次访存多2次，而又远少于二进制trie树的32次访存，这就保留了原来多分支trie树查询速度快的优点。
同时，普通的多分支trie树，对于前缀长不是整数倍的结点，要进行前缀扩充，最多扩充为2K-1个，占用了大量的存储空间，而本算法于没有对前缀进行扩展，占用空间小;而且更新结点不需要涉及到其他结点，和二进制trie树路由表更新的开销其实是一样小的。
5 结束语
本文在分析传统路由算法的基础上，提出了一种基于多分支trie树的路由查找算法。该保留了多分支trie树访存次数少，查询速度快的特性，并具有占用存储空间不大，更新开销小的特点，对IPv4和IPv6地址都可以使用。由于使用硬件实现往往能使得路由查找算法性能得到数量级的提升，接下来的工作可以在硬件实现技术上进行研究。
摘要：随着互联网络链路速率的不断提高, 路由查找已成为路由器报文转发的瓶颈。本文首先介绍和分析了路由器中广泛使用的各种典型IP路由算法方法, 并提出一种基于多分枝trie树的改进路由查找算法。该算法保留了多分支trie树访存次数少, 查询速度快的特点, 并具有占用存储空间少, 更新开销小等特点, 对IPv4和IPv6地址都可以适用。
关键词：因特网,路由查找,最长前缀匹配,trie树
参考文献
[1]Marc Friedman, AlonLevy, Todd Millstein.NavigationalPlans for Data Integration[C].Proc of t he16t h National Confon Artificial Intelligence (AAAI'99) [C].1999.6:72-73.
[2]A MCAULEY, P FRANCIS.Fast Routing Table Lookup using CAMs[J].Proc.IEEE INFOCOM1993, Vol3, pp1382-1391, San Francisco, USA.
[3]吴彤, 杨嗣超, 诸鸿文.路由表快速查找算法[J], 通信技术, No4, 2000:52-59.
[4]刘永锋, 杨宗凯.高速路由器中基于树型结构路由查找算法的研究与实现[J].计算机工程与科学.vol.26, No1, 2004:77-80.
[5]徐格, 吴建平, 徐明伟等.高等计算机网络-体系结构、协议机制、算法设计与路由器技术[M], 机械工业出版社, 北京, 2006:522-544.
[6]谭明锋, 高蕾, 龚正虎, IP路由查找算法研究概述[J].计算机工程与科学.vol, 28, No6, 2006:87-91.