多跳路由算法（共6篇）
多跳路由算法 篇1
0引言
地膜覆盖技术不仅可以减缓土壤水分的蒸发速度,而且可以起到抑制杂草生长、提升大田地温的作用,因此在我国北方干旱与半干旱地区的农作物种植中得到了普遍的推广和应用。虽然地膜使用较多,但地膜回收率较低。据农业部专项调查,每年残存在田间、土壤、沟河中的塑料薄膜至少占使用总量10% 以上,现累积残存量已在百万吨以上。残留地膜不仅会污染环境,而且能够造成农作物的减产。一般地膜的厚度较薄,容易断裂,回收难度较大,因此只有研究出新型实用的机具,才能加强对地膜的回收,保证农业的稳定持续发展,产生较好的经济效益和社会效益。
1地膜回收机总体设计
在国内,由于经济原因,一般种植采用的地膜厚度大约在0. 006mm,明显低于国际标准; 同时,使用的是不可降解的聚乙烯和聚氯乙烯高分子化合物,地膜经过播种和耕地及收获等环节,会产生断裂,较难清理,工作强度较大。本次研究拟通过设计,对地膜回收机进行改造,提高其工作效率。设计框架如图1所示。
为了使地膜回收机适应不同地块和不同地膜等具体工作环境,利用传感器对地膜的回收阻力进行采集,并据此实现伺服电机的转速调节,实现地膜回收机的自适应调速。为了提高工作效率,通过多跳网络对多地膜回收机进行协同控制,原理如图2所示。
地膜阻力由一台回收机的传感器进行采集,然后将采集信号传输给PC机进行处理; PC机通过多跳网络发出信号,对多台地膜回收机进行协同控制。
2机械结构和多跳路由控制算法设计
为了增强地膜回收机的通信能力,使其适应不同地膜密度的地块,提高地膜回收机的工作效率,需要对地膜回收机的机械结构进行改进。本次设计的地膜回收机应用在苗期地膜回收,其回收机的三维结构示意图如图3所示。
1.机架2.悬挂架3.卸膜胶带4.张紧轮5.卸膜轮6.集膜箱7.地轮8.起膜轮9.松土铲
苗期地膜回收机主要由7部分组成,主要包括机架、起膜轮、卸膜轮、卸膜胶带、集膜箱、松土铲及地轮。起膜轮和卸膜轮均由地轮驱动,在机具上安装有无线网络传感器,可以根据地膜阻力的大小采集地膜的密度信息数据。
图4为设计的残膜回收机的平面结构示意图。 其中,在起膜铲装的轴上装有力传感器,可以采集起膜阻力的大小数据。
1.机架2.传动部件3.地轮4.起膜铲5.切膜辊6.风道7.捡膜辊8.风机9.集膜袋
起膜铲的主要结构简图如图5所示。为了保证其能够起不同深度的地膜,需要将其设计能够深入到土壤内一定深度,且要尽量减少对地膜的扰动,深度设计为40mm,选取入土角 α 为28°,入土隙角 β 为8°。
1.侧导膜杆2.上导膜杆3.主支撑叉杆4.固定横梁
卷膜辊传动设计如图6所示。为了适应不同的起膜机速度,在卷膜机上装有速度传感器,可以对卷膜速度进行控制。为了保证起膜铲收起的地膜能及时被卷膜辊卷起,避免地膜滞留堵塞或拉断现象,则在相同时间内地轮前进距离应与卷膜辊卷起的地膜长度一致,即
其中,D为地轮的直径; d6为卷膜锟的直径; w1为地轮的角速度; w4为卷膜锟角速度; t为地膜回收机的前进时间。由于卷膜辊始终被紧压在卷膜驱动辊上, 因此两者的轮缘线速度相等,即
其中,d5为卷膜驱动锟的直径。由链轮和齿轮传动可得
其中,z1、z2、z3、z4分别为大、小链轮和大、小齿轮的齿数。综合上述公式可得
因此,主要满足改传动比,便可以实现顺利的卷膜。为了满足不同地块地膜顺利起膜的需要,需要设计无线传感器网络来使起膜机能够自适应不同地块的变化。在一定的通信范围内,可以将其应用在任意尺寸的地块内进行通信,根据公式( 2) 的计算,可以得到节点地址的偏移量如表1所示。传感器节点分布及通信范围如图7所示。
当B和C两个节点接受到A节点的通信请求后, 会向A点发出信息响应,并将通信深度定义为1; 同理,D和E两个节点在接收到A发出的通信请求后, 会将自身的路由深度定义为2。5个节点组成的路由表如表2所示。
在节点进行自组织通信时,节点可以收到同级或不同级的路由通信请求。为了节省通信能耗,可以选择最短的通信路径,然后更新路由表,从而大大提高了在不同地块通信范围内,地膜回收机的通信能力。
3基于多跳路由的地膜回收机性能测试
为了验证设计优化的地膜回收机性能,对地膜回收机进行了测试,以苗期地膜回收机为研究对象,在地膜机上装有无线传感器,并在地块内使用无线路由器等设备进行无线网络通信。地膜回收机性能测试如图8所示。
在地膜回收机上安装有多跳路由算法的通信系统,在100m × 100m的范围内使用5个无线路由器架构无线传感网络。为了测试不同通信半径的多跳网络性能,分布区半径R为15、20、25m,得到的网络节点终结数目与测试轮数的变化曲线如图9所示。由图9可看出: 在通信半径为25m时,性能达到最佳状态。
图10为使用和不使用多跳网络时节点的寿命测试曲线。由图10可以看出: 在3 500轮以内测测试使用多跳网络时期寿命周期要明显高于不使用多跳网络,从而验证了移动多跳网络性能的优越性。
图11为使用和不使用多跳网络时节点的能耗测试曲线。由图11可以看出: 在3 000轮以内测测试使用多跳网络能耗要明显低于不使用多跳网络,从而进一步验证了多跳网络的优越性,因此可以应用在地膜回收机的移动通信系统中。
表3为残膜回收机的回收率和作业时间的测试表。由表3可以看出: 残膜机作业的回收率较高,达到了90% 以上,其作业时间较短,在100 × 100m的作业范围内,作业时间不超过过13min,满足了高效残膜回收机的设计需求。
4结论
依据残膜回收机的作业原理,对起膜和卷膜机械装置进行了改进,使地膜回收机可以根据地膜的密度进行自适应的调节前进速度,提高了地膜的回收精度和回收效率。依据多跳网络的通信原理,设计了多地膜回收机协同控制网络,利用无线局域网,实现了地膜回收机的协同控制。对多跳通信网络进行了测试, 通过测试发现: 使用多跳网络通信可以有效地延长节点的生命周期,降低网络能耗。
多跳路由算法 篇2
关键词：网络生命周期,LEACHC,簇头,单跳+多跳
0 引言
现在大部分无线传感器网路路由算法都是从能量消耗的角度来进行研究的。在多数多跳路由算法中, 大量节点所采集的数据通过多跳的方式流向少数基站, 会造成距离基站较近的节点较早的“死亡”, 并且由于节点分布不均匀, 也会导致一些节点由于转发数据次数过多而过早的“死亡”。同样, 在一些单跳分簇算法中, 由于簇头融合数据之后直接与基站进行通信, 在小范围内能保证大部分簇头和节点间的通信满足自由空间模型。当范围变大时, 由于簇头节点间单次通信的能耗差别变得很大, 造成距离基站较远的节点过早的“死亡”同样影响网络的性能[1,2]。
在无线传感器网络中, 数据通信是系统最重要的操作之一, 并占用很大一部分的能量消耗。事实上, 在传感器网络中数据通信需要的能量远大于数据处理所需要的能量[3]。通过对各种无线传感器网络路由算法的研究, 本文提出一种能量均衡化分层式分簇单跳+多跳路由算法 (LEACH_C) , 引入了平均能量因素。该路由算法分为两级结构, 底层为传感器数据采集网络, 上层为数据融合转发网络。网络簇头分级结构如图1所示。
1 无线通信能量消耗模型
本文采用如图2所示的一种无线通信能量消耗模型。节点发送K比特的数据到距离为d的位置, 消耗的能量由发射电路的损耗和发射部分的功率放大器的损耗, 即:
其中Eelect表示发射电路的功耗, 当节点于节点之间传输数据时, 若传输距离小于阀值d0时, 采用自由空间传输模型;若传输距离大于d0时, 采用多路径衰减传输模型。εfs、εmp分别为两种数据传输模型中发射数据时功率放大器的功耗。
由式 (1) 可以看出, 在传感器节点之间进行无线通信时, 各节点之间的距离d是影响网络通信能耗的最主要的因素。
2 LEACH_C算法能耗模型分析
LEACH_C算法根据无线传感器网络的网络拓扑结构把网络分成两个层次, 传感器节点到路由转发节点和路由转发节点到基站。传感器节点到路由转发节点作为底层数据采集网络, 主要负责采集融合各个传感器节点收集到的信息;路由转发节点到基站为上层网络, 负责把底层网络收集到的信息转发到基站, 该过程由于信息量比较大, 转发次数比较多, 因此该层网络能量消耗占整个网络能耗的比重比较大。
2.1 传感器节点到路由节点
传感器节点到路由节点作为底层网络负责把传感器采集到的数据集中到路由设备。由于该层网络负责采集融合各传感器收集到的信息, 且分布比较均匀, 各节点之间的距离也比较小, 因此底层网络采用单跳固定分簇路由算法。路由转发节点作为底层网络的簇头, 负责融合数据并转发到上层网络, 各传感器采集节点通过单跳的方式把采集到的数据直接发送到路由转发节点。假设该簇的传感器节点的个数为i, 则底层网络的一轮数据传输的能量消耗为:
其中ETX, ERX分别为单个节点发送和接收k比特数据消耗的能量。d为各传感器到路由节点的平均距离。由于底层网络各节点之间的距离比较小, 因此采用自由空间传输模型, ETX, ERX分别为:
把式 (3) 带入到式 (2) 中, 则底层网络一轮数据传输的能耗为:
2.2 路由节点到基站
路由节点到基站作为上层网络负责把采集到的数据转发到基站, 由于路由节点的位置的不确定性, 也就是各路由节点间的距离d随机性比较大, 若简单的采用单跳分簇路由算法, 当网络范围变大时, 远离基站的节点能量消耗变大, 并且各簇头之间单次通信的能量消耗差别也会变大。其他LEACH相关多跳算法中, 由于每个簇成员个数不同就造成网络中能量消耗不均匀, 并且各簇头与基站进行通信时, 也没有限制多跳的次数, 这就使得基站周围的簇头由于参与较多的数据转发而能量消耗过快, 存在严重的“热点问题”。
综合以上各种问题, LEACH_C算法中采用不定长帧间隔的方式, 让簇成员比较少的簇内节点发送数据的间隔增大, 反之, 簇成员比较多的簇向基站发送数据的间隔减小, 这样在相同的时间内, 网络中大小不同的簇向基站发送数据的次数就基本一致, 很好的解决了网络中能耗不均的问题。同时, LEACH_C算法根据簇节点距离基站的距离d以及自己的平均剩余能量E (i) residual来决定该区域内的最优转发跳数, 并且在选择下一跳路由时, 充分考虑到路由节点的剩余能量状况, 这样不仅均衡了全网的能量, 同时也减少“热点问题”对网络生命周期的影响。
LEACH_C算法中最重要的是各路由转发节点多跳次数的确定, 不仅要考虑到各路由节点簇中簇头和簇内节点的平均剩余能量, 同时还要考虑各路由节点到基站的距离。现在我们假设有N个路由节点随机分配在半径为R的一个区域内, 基站位于该区域的中心, 根据路由节点到基站的距离远近把节点分成不同的区域, 分别为r1, r2, r3, .....rn, 如图3所示。
假设在区域R中有M个簇头, 平均分布在整个区域中, 位于rn区域的簇头节点和基站的通信需要rn-1区域内的簇头节点进行转发, 并且每次通信的距离都在自由衰减通信模型的范围d0内。为了便于研究, 假设每个簇头节点都位于各自区域的中部, 并且每个区域的环宽度都是r, 即r1区域的簇头处于r/2处, r2区域的簇头位于3r/2处, r2区域的簇头与基站进行通信时时通过r1区域的簇头进行转发的, 以此类推, 则当处于rj区域的簇头向基站发送k bit数据时, 网络中单个簇头节点的能耗为:
其中l是区域rj内簇头与基站通信时经过的跳数, 则经过一轮数据传输网络的整体能量消耗为:
把式 (4) , (5) 代入式 (6) 中有:
因此最优跳数即为使式 (7) 取得最小值时l的值, 这样就可以通过对Eall求关于l的导数来得出:
由式 (8) 可得:
由式 (9) 可知, 当 (i-1/2) r小于d0时, 也就是路由转发节点到基站的距离处于自由衰减模型范围内时, 采用单跳的方式进行数据传输, 反之, 则采用多跳的传输方式进行数据传输, 多跳的次数通过式 (9) 可以得出。这样, 上层网络的整体能量消耗就达到了最小状态, 但是一些“热点问题”还是没有得到很好的解决。
2.3 剩余能量均衡化
由以上分析可知, 单跳+多跳的路由方式虽然使整个网络的能耗降到了最低状态, 可是还是存在一定的“热点问题”会导致某些路由节点过早的“死亡”。LEACH_C算法中引入了节点剩余能量的因素, 即每个路由节点在向基站进行通信时, 把自身剩余能量同样发送给基站, 由基站进行分析统计出剩余能量比较大的路由节点作为簇头节点或者作为多跳路由的中间转发节点。
假设每个路由转发节点的初始能量为E0, 则一轮数据传输结束之后, 每个节点的剩余能量为:
其中m, n分别为节点i接收和发送k比特数据次数。每个路由转发节点在最后一次发送数据时根据式 (10) 计算出自己的剩余能量Ei, 和数据一起发送出去, 基站接收到各个节点的能量信息之后进行分析, 统计出各个区域内Ei的最大值, 然后根据LEACH_C路由算法对各区域广播信息。这就很好的解决了一些转发节点的受到“热点问题”的影响而过早死亡的问题。
3 LEACH_C算法仿真
如图4所示, 通过MATLAB进行LEACH_C算法的仿真, 并同LEACH以及DEEC算法从网络生命周期以及数据传输数量上进行了比较。仿真场景为100*100的环境中, 基站位于 (50, 50) , 节点个数为100个。通过时间周期轮数和死亡的节点数量来描述网络的生命周期。图4显示了LEACH_C算法和LEACH算法网络生命周期的对比。
同样, 把LEACH_C算法和DEEC算法也进行比较, 如图5所示。
由图4, 图5可以看出, LEACH_C算法生命周期明显优于LEACH算法和DEEC算法。其第一个死亡节点出现在800轮数据传输之后, 说明整个网络的能量均衡性能取得了比较理想的效果。LEACH_C算法仿真到1200轮左右时, 其死亡节点分布如图6所示。其中红色节点表示死亡的节点, 由图中可以看到死亡节点的分布还是比较均匀的, 并没有出现死亡节点扎堆的情况, 这就说明LEACH_C算法对“热点问题”的解决也是比较理想的。
4 结论
综上所述, LEACH_C算法中传感器节点到路由节点网络通过固定的单跳分簇结构进行传感器信息采集;路由节点到基站网络根据他们与基站的距离划分为不同的区域, 根据式 (9) 以及式 (10) 的策略确定数据转发的次数, 以减轻基站周围区域的节点能量的负载。并且LEACH_C算法使用不定长帧间隔, 进行每轮数据收集时, 单个路由转发数据的次数大致相同, 解决了因簇成员不同引起的负载分布不均衡的问题;另外, 在路由选择过程中, 也充分考虑路由下一跳的节点能量消耗和剩余能量的情况。因此, LEACH_C算法能够使网络中的簇头节点的负载趋于均衡, 有效的减弱了“热点问题”, 同时也降低了离基站较远的簇头的通信能耗;同时该算法还限制路由转发时的距离, 降低了中间节点的电路开销, 使离基站较近的区域的路由簇头节点和基站通信, 再由基站将路由信息传递给紧邻的下一区域的簇头节点, 避免了路由选择时产生的能量浪费。LEACH_C算法很适合应用于智能服装、智能环境监测, 矿井下监测等低能耗分层网络, 具有很好的研究价值。
参考文献
[1]W.Heinzelman, A.P.Chandrakasan, H.Balakrishnan.Application-specific protocol architecture for wire-lessmicrosensor networks[J].IEEE Transactions on WirelessCommunications, 2002, 1 (4) :660-670.
[2]G.Pottie and W.Kaiser, Wireless integrated networksensors, Communications of the ACM, 43, (2000) , 51-58.
[3]J.C.Zhao, A.T.Erdogan, T.Arslan.A Novel ApplicationSpecific Network Protocol for Wireless Sensor Network[J].Circuits and Systems, 2005:5894-5897.
[4]任东海, 尚凤军, 王寅.一种基于时间延迟机制的无线传感器网络分簇算法[J].传感技术学报, 2009, 22 (11) :1645-1649.
多跳路由算法 篇3
WSN是具有数 据融合、 通信和计 算等特定 功能的节点 以自组织 的形式关 联在一起 的网络体 系 ,能够实时 监测、感知 和采集周 围环境的 相关信息 , 并把信息 经过处理后 通过路由 协议传输 给终端计 算机[1]。WSN在环境监测 、智能交通 等领域得 到了广泛 的应用[2,3]。
由于三维 空间的路 由协议更 符合实际 的应用环 境 ,近年来其 成为WSN研究的热 点。Li等人在文 献[4]中提出3D-SAEAR算法 ,通过迭代 分簇方法 一定程度 上平衡了网 络的能耗 , 但是簇首 死亡时才 发动选举 , 造成节点过 早死亡。Ke等人在文 献[5] 中提出了 三维胞元 空间模型和3D-CSR算法 , 建立了完 整的分层 路由体系 , 提出了自适 应选举机 制 ,但是采用 贪婪路由 方式选择 邻居胞父节 点中到目 的节点的 距离最短 的作为下 一跳节点 (此节点为邻 居最优胞 父 ), 没有建立 有效的能 量模型来 优化传输路 径 ,导致平均 能耗较多 。
3D-SAEAR算法和3D-CSR算法均存在簇首负担较大的问题, 本文在三维胞元空间模型的基础上, 提出了3DSMEER算法。该算法引入协同节点协助最优胞父转发消息包,减少了总的路径损耗,降低了网络的能耗;建立协同节点选举机制,保护了能量较低的节点,提高了能量利用率。
1 算 法模型
1 . 1 能 耗 模 型
当传输g bit字节时 ,总能耗Es表达式如 下所示[6]:
其中l表示节点 之间的距 离 ,Eelec表示发送1 bit字节时 ,启动电路 能耗 ,εamp为放大电 路能耗 ,γ为路径 损耗指数。 本文假设 在自由空 间模型下 ,取γ=2。
1 . 2 协 同 节 点 选 择 模 型
Bhardwaj等 [7]提出当采 用最佳传 输距离Lideal转发消息包 时 ,通过最佳 跳数Hideal, 能耗达到 最低 , 由Lideal确定的转发 位置称为 理想转发 节点位置 ,Lideal和Hideal表达式分别为 :
WSN中一般达 不到转发 节点相互 距离为Lideal的要求 ,因此提出协 同节点代 替理想转 发节点多 跳传输的 模型。
基于协同 节点的多 跳模式的 基本思想 为 : 首先在贪婪 策略下确 定邻居最 优胞父 ,根据Lideal确定理想 转发节点位 置Mi; 然后以Mi为球心 , 作半径为r的球体 , 球体内的节 点称为候 选协同节 点 ;最后根据 协同节点 的选择原则 进行选举 :
( 1 ) 低剩余能 量保护原 则 : 低剩余能 量保护系数 为β (0<β<1), 节点的初 始能量为Eini, 如果节点 剩余能量Eres< βEini, 则该节点 不能作为候 选协同节 点。
( 2 ) 重复选择 避免机制 : 球体半径r值增大时相 邻球体出 现相离、相 切与相交 的三种关系 ,若某节点 被选中为 协同节点 后不能作 为另外球 体的候选协 同节点。
( 3 ) 胞父优先 原则 : 球体中有 胞父节点 , 则优先选 择胞父作为 协同节点 。
( 4 ) 能耗节省 原则 : 同类型的 节点比较 时 , 优先考虑与 理想节点 位置距离 最短的节 点为协同 节点。
LEN ( A , B ) 表示节点A与节点B之间的距 离。图1为通过协同节点转发的示意图,其中LEN(C,M1)=LEN(M1,M2) = Lideal, d表示胞元 的边长 , 当前胞元 ( XI, YI, ZI)C中胞父节点C确定的邻 居最优胞 父P位于胞元 (XJ, YJ, ZJ)C内。球M1内有胞父 节点 , 由原则 (3) 选择胞父 为协同节点 ; 球M2内无胞父 节点 , 由原则 (4) 选择距离 理想转发节 点最近的 胞子为协 同节点。
2 3D - SMEER算法
该算法根 据自适应 多跳机制 决定传输 方式 , 利用协同节 点选择机 制选出转 发节点协 助当前胞 父传输消息 包。
2 . 1自适应多 跳机制
由公式(3)知 ,当前胞父 和邻居最 优胞父的 距离L与最佳传输 距离Lideal的关系决 定了最佳 跳数Hideal。图2 ( a )中当L<Lideal时 , 采用单跳 的方式到 达邻居最 优胞父 ;图2 ( c ) 中当L > 2Lideal时 , 由公式 (3) 得Hideal≥2, 即采用多 跳方式把消 息包传输 给邻居最 优胞父 ; 图2 (b) 中当Lideal<L < 2Lideal时 ,比较二者 传输消息 包的能耗 , 协同节点 位于M1处时 ,根据公式(1)计算比较 两跳能耗E2h和单跳能 耗E1h得 :当L>1.5 Lideal时 ,E1h> E2h, 即多跳能 耗更小。 但是理想转 发位置处 一般不存 在节点 ,所以采用 协同节点 进行多跳的最小距离为Lmin= 准Lideal( 1 . 5 < 准 < 2 ) , 即当L < Lmin时直接传输 ,否则选择 协同节点 转发传输 。
2 . 2协同节点 选择机制
选择协同 节点时需 要确定协 同节点的 选择范围 , 即球体的位 置和半径r。
2 . 2 . 1 球 体 半 径 r 的 确 定
理想转发 节点空间 坐标即为 球心位置 , 在图1中设邻居最 优胞父节 点为P, 其坐标为 (XP, YP, ZP) , 同时令当前 胞元(XI,YI,ZI)C中胞父为M0, 其坐标为 (XM0,YM0,ZM0) ,理想转发 位置处球 心Mi的坐标为 (XMi, YMi, ZMi) 。以Mi的X轴坐标XMi为例 ,表达式为 :
其中i∈N且[1,Hideal- 1 ] 。
对于节点 密度较小 的网络 ,r值过小 ,球体内找 不到协同节 点 ;反之 ,会增加传 输路径。 假设存在rmax使r<rmax时 ,通过协同 节点进行 多跳比单 跳能耗更 少。为了 求得rmax考虑一种 极限情况 , 即所有的 球体内只 存在一个 协同节点 , 且位于球 体边缘 , 即图3 (b) 是由图3 (a) 投影到XOZ平面所得 。在图3(a) 中 , 节点C为当前胞 父 , 协同节点J位于球M1的边缘处 ,节点P为邻居最 优胞父 ,α = ∠CM1J , d表示LEN ( C , P ) , d1表示LEN (C ,J) ,d2表示LEN ( J , P ) , 通过节点J传输和直 接传输的 能耗分别为 :
当cosα=1时 ,即节点J位于W点处时E2h取得最大值 ,此时可得 到rmax表达式为 :
考察式 (7) 得 ,0.5 Lideal< rmax< Lideal, 实际情况 中选择球 体半径r=φrmax( 0 . 5 < φ < 1 ) , 其中φ称 为球体半 径调整系 数。
2 . 2 . 2 协 同 节 点 的 竞 选 法 则
协同节点 的区域确 定后 , 由低剩余 能量保护 原则和重复 选择避免 机制确定 候选协同 节点。结 合协同节点 选择原则 , 提出候选 协同节点G的竞选权 重( Election Weight , EW ) , 其表达式 为 :
其中G表示当前 候选协同 节点 ,n表示候选 协同节点 总数 ,K[j] 表示球体 中第j个候选协 同节点 ,LEN(K[j],Mi)表示球体Mi中第j个候选协 同节点与 球心Mi的距离 ,Eres ( K[ j ] )表示第j个候选协 同节点的 剩余能量 ,权重系数 λ和η的关 系为 :λ+η=1(0≤λ≤1,0≤η≤1)。其中θ 的取值遵循 以下原则 :当球体内 候选协同 节点是同 类型的节点 , 即都是胞 子或者胞 父节点时 θ =1; 否则 , 胞父节点θ = 1 , 胞子节点 θ = 0。
协同节点 竞选法则 : 将球体内 每个候选 节点的剩 余能量和空 间位置带 入式(8)中 ,按照上述 原则比较 球体内候选 节点的EW, 最后选择 出EW值最大的 作为本球 体的协同节 点。
2 . 3 3D - SMEER算法的具 体过程
结合自适 应多跳机 制和协同 节点选择 机制 , 总结出基于 协同节点 多跳路由 的步骤为 :
( 1 ) 根据贪婪 策略 , 判断出邻 居最优胞 父P , 并计算LEN ( C , P ) 。
( 2 ) 由自适应 多跳机制 判断采用 多跳或者 单跳 , 如果结果为 单跳则直 接把消息 包传递给 邻居最优 胞父P, 否则进入步 骤(3)。
(3) 利用协同节点选择机制确定球心的空间位置和协同节点的选择范围,然后根据低剩余能量保护原则和重复选择避免机制确定是否存在候选协同节点,若不存在则直接把消息包传递给邻居最优胞父P,否则进入步骤(4)。
( 4 ) 依据候选 节点的EW选择出协 同节点 , 将消息包通 过协同节 点转发给 邻居最优 胞父P。
具体流程 如图4所示。
3 仿真实验
3 . 1 仿 真 环 境 及 参 数 设 置
仿真是在OMNet++ V4.1平台上进 行的 , 节点分布在 体积为400 m×400 m×400 m的立方体 内。与3D-CSR和3D-SAEAR进行仿真 结果比较 时 ,为了使仿 真结果更有 可比性 ,假定消息 包只按照 贪婪模式 进行传输 。参数设定 如表1所示。
3 . 2 仿 真 结 果 分 析
仿真结果 将通过平 均能耗和 节点存活 率进行对 比。平均能 耗 (average energy consumption) 为传输k条消息包所 消耗的总 能耗与k的比值 ; 节点存活 率 (Alive rate) 为传递k条消息包 后存活节 点占总节 点数的百 分比。
3D - SMEER , 3D - SAEAR与3D - CSR的平均能 耗曲线如图5所示。3D-SAEAR与3D-CSR相比增加 了角度机制 ,所以其平 均能耗比3D-CSR略有减少 。3D-SMEER通过协同 节点转发 消息包 , 相比3D-SAEAR与3D-CSR有效降低 了平均能 耗。图5(a) 和图5(b) 中每个胞 元的节点个 数N分别为2和4, 随着N的增加 ,3D-SMEER增加了中 间协同节 点的个数 , 使得传输 能耗减少 , 所以图5(a) 和图5(b) 中3D-SMEER的平均能 耗是逐渐 降低的 ,而3D-SAEAR与3D-CSR的平均能 耗基本不 变。
三者的节 点存活率 与消息包 的关系如 图6所示。图6 ( a ) 和图6 ( b ) 中胞元的 节点数N分别为2和4 , 3D - CSR通过自适 应胞父选 举平衡了 网络的能 耗 , 所以3D-CSR与3D-SAEAR相比提高 了节点的 存活率 , 并且随着 胞元内节点 数N的增多 , 选举机制 能够发挥 更好的作 用 ;3D - SMEER与3D - CSR相比 , 通过协同 节点转发 消息包 , 降低了邻 居最优胞 父的传输 负担 , 从而提高 了网络节点 的存活率 , 当网络的 节点密度 增加时 , 增加了其 他节点参加 传输消息 包的概率 ,所以提高 了存活率 。
4 结 论
多跳路由算法 篇4
无线传感器网络 (Wireless Sensor Network, WSN) 是部署在监测区域内大量的传感器节点以自组织方式构成的无线网络。WSN具有展开快速、抗毁性强、检测精度高、覆盖区域大等特点, 在军事、航空航天、环境监测等领域具有广阔的应用前景。但传感器节点在计算、通信能力及能量等方面都十分有限, 再加上部署环境多在人们不易到达的地方, 使得节点的更换和充电也较难实现。因此, 如何减少节点能耗、延长网络生存时间是目前研究的热点问题[1]。对此, 国内外学者提出了一系列的解决方案, LEACH (low-energy adaptive clustering hierarchy) 协议提出了分簇思想, 实现了载荷均衡[2];HCCM协议采用了正六边形分簇的方式, 实现了多跳传输[3]。这两种协议都是先确定好簇的划分, 再收集数据, 这样划分的灵活性不强, 可能造成不必要的资源浪费, 而且, 在大规模无线网络环境中, 簇头与基站之间的距离一般较远, LEACH采取簇头与基站单跳通信的方式将会造成因簇头能量不足, 无法与基站通信而产生“死亡簇”的情况[4]。虽然在HCCM中簇头与基站之间通信时采用多跳方式, 节省了能量, 延长了簇的生命力, 但这种做法会使得离基站近的节点因为转发大量数据而过早耗尽能量, 从而失去工作能力。
为了改善这些情况, 本文提出了基于事件触发的六边形分布式分簇多跳路由协议, 该协议采用6个点构成六边形, 这种方式增加了网络的容错性, 使簇内成员能够灵活地被簇外成员替换。HDCMET协议由事件触发节点, 只有当事件进入监测区域, 才能使位于监测范围内的节点被激活, 而其余节点仍处于休眠状态。此外, HDCMET协议使用编码分区的方式, 将信息从簇头向基站多跳传输。 Matlab仿真结果表明, 在大规模随机分布的无线网络中, HDCMET协议能增加节点使用率, 有效延长网络生存时间。
1分簇多跳路由协议
1.1网络模型
假设有大量传感器节点随机均匀分布在一个正方形区域内, 基站的位置位于正方形区域的一角上。在网络建立之初, 基站会根据各节点的位置, 设置一个标志 (用0、 1、2…表示, 数字越小表示距离越近, 基站标志为0) , 基站将与其距离相近的节点用统一的标志表示出来, 并通过广播的形式将标志发送给各个节点。
结合HDCMET协议的特点, 现对无线网络传感器作如下假设[5]:1网络中的全部节点是随机分布的, 初始能量相同, 节点的坐标由定位算法获得;2因为基站不靠电池供电, 这样就可以认为它的能量是无穷的;3节点的发射功率可根据通信双方之间的距离来动态调整;4各个节点的监测半径R0相同并已知, R0不随能量、温度等外界因素的变化而变化。
1.2基于事件触发的六边形分布式分簇算法
当事件进入监测区域后, 处于休眠状态的传感器被激活。此时, 被激活的传感器先将自己的剩余能量与Er (能量阈值) 进行比较, 当小于Er时不发送自身位置等信息, 当大于或等于Er时才广播自己的位置、ID号和剩余能量。当节点接收到其余节点发来的信息时, 先提取剩余能量, 将其和自身保存的最大能量Emax进行比较, 如果大于Emax, 则修改最大能量值, 并保存其位置信息;如果小于等于Emax, 则丢弃该信息[5]。被事件触发的传感器数目有限, 这样可以保证经过一轮比较后, 在所有被触发的节点中, 最大能量节点的信息是一致的。所以, 选取出来的簇头不用进行声明, 其余节点可以及时向簇头发送数据。而后, 簇头收集其余各节点发来的信息, 根据它们的距离、剩余能量和数据采集量选择出最接近正六边形的5个节点。 具体算法如下:
根据正六边形的几何特性, 构建的正六边形是以检测半径为边长。簇头先以自身为圆心, 以监测半径R0为半径, 选取在该范围内的节点, 再利用公式 (1) 对节点进行筛选。公式 (1) 的具体算法为:
设节点i的剩余能量为Ei, 数据采集量为Si,
其中, Pei= E0/E;Psi=Si/S0;.E0、S0分别为初始能量和假定最大数据传输量, α和β分别表示Pei、Psi的权重, 且α=0.6, β=0.4。
簇头选择距离最接近R0且Pi最大的两个节点, 作为与簇头相邻的节点, 而后这3个节点利用公式 (1) , 分别找与其距离为2 R0的节点。当完成筛选后, 与簇头相邻的两个节点把选择的结果发送给簇头。簇头接收到这些信息后, 将选择的结果广播出去, 未被选中的节点进入休眠状态。这样建立的六边形最接近正六边形, 其监测面积约为
当节点的剩余能量小于等于Emin (最低能量值) 时, 节点停止采集信息, 并唤醒最近的节点, 使其代替自己继续工作。新进入的节点先主动将自己的位置和ID号发送给簇头, 让簇头明白之前的节点已经失效, 而后, 新节点直接进行数据采集, 把数据发送给簇头。在替换过程中, 不必担心数据采集不完全, 因为6个节点采集的数据高达5.6%左右的冗余度, 可以允许部分节点的位置偏移。但如果簇头的能量小于或等于能量阈值Er, 则其会广播发送重新竞争簇头的信息, 簇内的5个节点接受到这个信息, 则停止数据采集。之前被事件激活的簇外节点再次激活, 进入下一轮的簇头选择。
1.3多跳路由选择算法
节点编码是一种新型节点位置标识方式, 融合了编码和路由选择的概念, 可以在数据传输中减小传输距离, 降低能耗, 减缓信号衰减的速度[6]。基于这一观点, 本文提出基于节点编码的多跳路由算法。
在网络成立之初, 基站会收集各个节点的位置信息, 并以自身为圆点, 以节点的监测半径R0的整数倍为半径, 依次编号。即半径为R0时编号为1, 半径处于R0与2R0之间编号为2, 以此类推。
已知基站对各节点的编号, 当某一标志的节点 (簇头) 要向基站发送数据而自身能量不足以将数据发送过去, 即Er
1.4能耗分析
节点的能量消耗主要在于数据的传输和处理。对于服从四次方衰减的无线电, 每100m距离上传输lkb数据所消耗的能量大致相当于在100MIPS/W的处理器上执行300万个指令, 即节点的数据处理能耗要远小于数据收发能耗, 因此, 本文主要考虑数据收发能耗。
结合HDCMET协议的分簇特点, 根据通信双方的位置, 可分为簇内通信和基站通信。在簇内通信中, 簇内成员会根据其与簇头的距离调整发射能量, 并以单跳的形式进行传输。在与基站通信时, 簇头采用多跳路由算法, 在其最远发射范围内选择合适的节点, 进行下一跳传输。
本网络采用无线通信方法, 通过设置传输距离门限d0, 分别采用自然空间模型和多径衰落模型, 假设节点发送k bit数据, 数据传输距离为dm, 此时消耗的能量Etx为[7]:
传感器节点接收k bit数据所需要的能量Erx为:
其中, Eelec是发送电路和接收电路的能量消耗;εfs和 εmp分别是自由空间模型和多径衰减模型中功率放大器的能量消耗, d0是传输距离门限, 为R0的两倍, 决定了衰减模式。
2仿真结果与数据分析
HDCMET协议利用Matlab进行仿真, 将HDCMET协议与LEACH协议进行比较, 结果见图3。其中, 相关参数定义为:正方形监测区域边长a=200m, 基站位于 (190, 190) , 节点数目为N=1000, 各个节点的监测半径R0=10m, 节点初始能量E0为2J, 数据包长度 (即最大传输量) S0=5000bit。
由图3 (a) 所示, 采用HDCMET协议传输数据明显多于LEACH协议。因为数据处理具有突发性, 不能事先预测数据传输的路径, HDCMET协议的数据采集是基于事件触发机制的, 能有效应对突发数据的采集和传输, 而LEACH协议是通过事先选择好的路径进行传输, 容易出现路径选择不合理的情况, 降低传输效率。
从图3 (b) 可以发现, 在相同节点数目内, 采用HDC- MET协议存活的节点数明显高于LEACH协议, 而且整体节点的存活时间也长于LEACH。这是由于HDCMET协议是根据事件触发节点进行信息监控和发送, 而不是像LEACH协议那样, 由基站按照时间轮进行统一分簇, 即使没有事件发生, 节点也要接受分簇信息, 避免了不必要的能量消耗。同时, HDCMET协议采用分散式算法, 由节点自身分析、计算并分簇, 增加了分簇的灵活性, 避免了大规模网络中因节点数目众多而造成的重复数据采集问题, 减少了整体节点的能耗, 而且, 数据的冗余性也使簇内节点能够灵活替换, 减少了重新建簇的机会, 节省了能量消耗, 延长了网络的寿命, 从而增加数据传输量, 提升网络性能。
3结语
HDCMET协议在大规模的随机均匀分布的无线传感器网络中, 能明显延长网络寿命, 而且该协议采用事件触发机制, 节省了大量节点。HDCMET是以六边形为基础的, 既保证了数据采集的完整性, 也为其容错性提供了一定的数据冗余[8]。虽然基于事件触发的六边形分布式分簇多跳路由协议对于大规模随机均匀分布的无线传感器网络有较好的适应性, 但是, 由于该协议中分簇划分是由簇头完成的, 这样容易造成单个节点负担较大, 对此还需要进一步深入研究。
参考文献
[1]GUAN XIN, WANG YONGXIN, LIU FANG.An energy-efficient clustering technique for WSN[C].International Conference on Networking, Architecture, and Storage, IEEE, 2008:248-252.
[2]陈静, 张晓敏.无线传感器网络簇头优化分簇算法及其性能仿真[J].计算机应用, 2006, 26 (11) .
[3]李桢, 陈健, 阔永红.WSN中六边形集中式分簇多跳路由协议[J].西安电子科技大学学报, 2012, 39 (3) .
[4]伍小平.传感器网络分簇路由协议的研究与仿真[D].武汉:武汉理工大学, 2005.
[5]YANG YINGTANG, GAO XIANG, CHAI CHANGCHUN, et al.Novel dynamic routing algorithm for energy optimization in WSN[J].Journal of Xidian University, 2010, 37 (5) .
[6]林力伟, 许力, 潘鹏贵.基于网络编码的分簇传感器网络链路容错策略[J].计算机应用, 2010, 30 (1) .
[7]裴晓黎, 刘志坤, 刘忠.事件触发的无线传感器网络动态分簇[J].舰船电子工程, 2012, 32 (2) .
多跳路由算法 篇5
无线传感器网络集成了传感器技术、嵌入式系统技术、微机电系统技术、分布式信息处理技术以及无线通信技术,有着不可估量的应用前景。无线传感器网络采用的传感器体积小、能量少、节点部署环境较差[1]。对于能量受限的无线传感器网络来说,在确保网络应用的前提下节约能量消耗是一个关键问题。通过拓扑控制技术生成优化的拓扑结构可以实现节约能源消耗。
1 LEACH算法的特点
LEACH算法自适应性好,容错性高,并且能够有效的延长网络的寿命[2]。但是这种算法也存在着自身的缺点:
(1)簇首节点分布不合理。由于簇首产生的随机性会导致整个网络分簇不均匀,致使部分簇首相距基站远近不一,从加重某些簇首节点的负担,降低网络负载平衡度。
(2)簇内节点分布不均匀。因为是随机性的产生簇首,所以就可能造成簇首负担的节点不均衡,网络拓扑结构分布不均匀使得簇首节点消耗能耗不一,造成网络能量负载不平衡,减少了网络生存时间。
(3)簇首选举中没有考虑节点的剩余能量,剩余能量少的节点一旦当选为簇首,会导致该簇失效,甚至网络瘫痪。
(4)簇内节点Hj直接把数据传输给簇首节点CHi,当两者之间的距离较远时,会加重簇内节点的能源消耗以及簇首节点的能源消耗。
2 系统模型
本文采用文献[3]中的无线通信能量消耗模型,节点发送l bit的数据所消耗的能量为ETx(l,d),由发射电路损耗和功率放大损耗两部分组成,即公式(1)所示:
Eelec表示发射电路和接收电路损耗的能量消耗,在该模型中两者取相同值,能量消耗值与消息长度l成正比。功率放大时的能量消耗与发射节点和接收节点之间的传输距离d有关。根据传输距离d与给定阈值d0之间的关系,发送节点选择不同的能量衰减模型计算发送数据所消耗的能量,即当传输距离小于d0时,采用自由空间模型,发送数据的能量消耗与距离的平方成正比关系;否则采用多路径衰减模型,与距离的四次方成正比关系,如公式(2)所示:
其中εfriss-amp、εtwo-ray-amp分别表示这两种模型功率放大所消耗的能量,d0=4πhrht/λ,ht和hr分别表示发射装置和接收装置的天线长度,λ表示标志信号波长。
接收装置每接收l bit数据的能量消耗为:
3 LEACH-EAM算法的实现
LEACH-EAM算法采用LEACH算法中轮次转换的方法,把每轮循环分为簇的建立阶段和稳定的数据通信阶段,如图1所示。
3.1 簇的建立阶段簇的建立阶段由簇首确定和簇的形成两个阶段组成。
3.1.1 簇首确定
在簇首选举上,算法采用基于节点密度争先的簇首选举以及允许已经充当过簇首的节点继续参加选举的方法。同时,引入节点当选簇首次数限制F(i)和能量限制Et(i)两个指标,避免节点频繁当选簇首或者剩余能量少节点当选簇首,造成节点加快死忙的问题。
簇首选举时节点生成介于0-1的随机数a,用a与簇首选举阀值T(Ni)进行比较(T(Ni)由公式(4)定义),a比T(Ni)小就具备当选簇首的先决条件。
在公式中:P是一个0-1间的实数,为网络中每轮节点成为簇首占所有节点的比例;r是当前轮数;G是在前r-1轮内未死忙节点集合,D(Ni)是节点密集度参数(由公式(5)定义)。
Nd(i)为节点i的存活邻居节点数。
公式(5)由LEACH算法公式修改而来,它与LEACH算法不同的是:(1)LEACH算法中禁止当选过簇首的节点再次参选,会从另一方面造成簇首节点分布在网络边缘,网络分簇不均匀,所以本算法的簇首选举阀值把限制当选过簇首的限制条件去掉,允许节点多次单选簇首;(2)增加密度集参数,由1-D2(Ni)可以看出,随着节点周围存活的节点数越多,1-D2(Ni)的值也就越大,节点当选簇首的概率也就会越高,节点周围存活的节点数越少,节点当选簇首的概率也就会越低。而且每个节点密度集也会随着时间的变化而发生改变。
算法在簇首选举的过程中还要衡量节点当选簇首次数限制F(i)和能量限制Et(i)两个指标,定义以下变量C(i),ei,Eavr。C(i)是节点在生命期内中当选簇首节点的统计次数,由节点通过累加得到,ei为节点剩余能量,由节点自己能量消耗情况得出,Eavr为全网存活节点的平均剩余能量,由Sink节点返回得出。其中
RMAX为系统设定的最大选举轮数,参数P为系统设定的最优簇首比例。节点只有在指标F(i),Et(i)都比实数1小的时候才具备当选簇首的前提条件。通过指标F(i)可以保证节点当选簇首的次数控制在一定的范围内,避免节点过早死忙。通过能量限制Et(i)保证当选簇首的节点剩余能量必须比全网存活节点的剩余能量大,避免剩余能量较少的节点担任簇首。
在簇首选举的过程中从节点密度集、节点当选簇首次数限制和能量限制等三个方面对LEACH算法进行改进,簇首的选举不再是单个节点的事情,而是周围节点的联合考虑。簇首选举流程图如图2所示。
3.1.2 簇的形成
一个节点成为候选簇首节点后,就向其邻居R范围内广播成为获胜簇首的消息,该消息包括节点的ID,剩余能量ei和坐标,等待节点的加入。非候选簇首节点收到簇首的广播消息后,则计算与每个候选簇首之间能量距离综合权值参数wji(wji由公式(8)给出),选择wji值大的簇首加入,如果存在与多个候选簇首节点的wji值相等,则选择距离短的簇首加入,并向该簇首发回确认消息,确认消息包含节点的ID,剩余能量ei和坐标[4]。
其中ej为非簇首节点的剩余能量,d(j,i)为非簇首节点Hj与簇首CHi之间的距离。
节点在簇首选举时间内如果没有收到来自候选簇首的消息,则该节点宣布成为簇首,并向其邻居R范围内广播当选簇首的消息,该消息包括节点的ID,剩余能量ei和自身的地理位置,等待节点的加入,只有与该节点相同的没有收到获胜簇首消息的节点才需要对这条消息响应,通过前面的能量距离综合权值参数wji方法选出剩余的簇首。
3.2 稳定的数据通信阶段
LEACH-EAM算法在稳定的数据通信阶段簇内数据传输采用多跳和单跳结合的方法。LEACH-EAM需要根据当前条件是否满足临界条件来决定簇内节点进行多跳或者多跳的数据传输。
3.2.1 临界条件
临界条件的确定参考文献[5]得出,在文献中通过参数Qcluster(公式(9))确定临界条件。
Qcluster为每个簇平均所占的面积。簇所覆盖面积大小决定了该分簇是采用多跳或者单跳的传输方式。当簇所占的面积满足大于Qcluster时,采用多跳的传输方式,反之则采用单跳。
3.2.2 多跳的实现方法
在实现多跳的数据传输过程中,簇首CHi先根据簇内成员节点的位置信息,采用最短路径算法Dijkstra计算连接边的权重意义上的最短路径得到CHi出发到所有簇内节点的路由路径树。根据公式(2)可计算连接边的权重Eelec+εfriss-ampd2,因为簇结构中传输距离较短的特性,所以衰减因子选择2。当最短路径计算完毕后,簇首CHi将路径树打包成消息广播给簇内节点[5]。簇内节点Hj接收到路径消息后,可从消息中得出自己的上一跳集合和下一跳集合。
4 算法仿真
4.1 仿真系统配置
仿真系统配置如下:传感器网络布置区域为100m×100m,随机分布的节点数为100个,基站位置固定在坐标(50,50)处,节点的传输距离为10m—50m,节点初始能量为2J,节点接收和发送电路消耗的能量Eelec为50Nj/bit,信号放大器的放大倍数为0.0013pJ/bit/m4,增量Δ为2,EDA为0.009J/bit/signal,节点充当簇首时间为100s[6]。
4.2 性能分析
为了评价算法对网络性能的影响,为了更好地衡量网络寿命、能量利用率和簇规模等几个指标,本仿真实验中测定了四个指标,分别为:簇规模、网络寿命、簇内节点分布、平均功耗。
4.2.1 簇规模
簇规模指标用来评价各簇节点数的平衡度。为比较LEACH-EAM算法在平衡各簇规模的作用,随机抽取了算法在运行过程中的分簇,如图3所示。可以看出LEACH-EAM结合节点剩余能量和节点密度选择簇首,相比LEACH算法和DBPC算法簇首节点分布比较均匀,而且都分别位于各簇的中央地带,较好地避免了簇首节点聚集或处于网络边缘的问题。
4.2.2 不同簇首比例网络寿命
图4为簇首比例P分别取0.04、0.05、0.1时,四种算法对网络寿命的影响。可以看出在3种不同簇首比例P下,因为LEACH—EAM算法在簇首选举阶段引入能量限制指标,避免剩余能量少节点当选簇首,在簇的形成阶段,非簇首节点计算与每个候选簇首之间能量、距离综合权值,并加入选择综合权值大的簇,簇内节点采用多跳与单跳相结合的方式进行数据传输,所以网络寿命最长,OBCP次之,LEACH的网络寿命最短。而且当P=0.04时,LEACH-EAM的网络存活时间最长。
4.2.3 簇内节点分布
簇内节点分布性能指标反映网络分簇情况是否均衡。如图5所示,可以看出LEACH-EAM各簇包含的节点数相对于LEACH、DBCP更加集中,从而进一步证明通过结合节点密度选举簇首可以更有效平衡各个簇的规模。
4.2.4 不同网络直径下的网络寿命、节点平均功耗
图6和图7分别表示在不同网络直径下的网络寿命和节点平均功耗的对比情况。从图中可以看出,随着网络直径的增加,簇内通信距离增大,造成簇内消耗的能量也增大,LEACH-EAM相对LEACH算法、DBCP算法节点平均功耗是最少,网络寿命最长。
5 结束语
本文LEACH算法进行深入研究,提出了LEACH-E-MA算法。通过簇首的确定、簇的形成两个阶段,簇内数据传输方式实现了改进算法,具备网络分簇情况均衡,节点的平均功耗少;网络的生存时间长的特点。
摘要：拓扑控制是无线传感器网络技术中的一个重要研究方向,良好的拓扑控制机制能够提高路由协议和MAC协议的效率,为数据融合、时间同步和目标定位等很多方面提供基础。本文在提出一种基于能量有效和多跳的层次型拓扑控制算法。算法在簇首选择阶段综合考虑节点剩余能量、节点密度、节点间距离,在非簇首节点加入簇阶段综合考虑节点间剩余能量及距离,数据传输阶段根据临界条件来决定簇内数据传输采用多跳或者单跳的数据传输的机制。通过仿真软件验证发现算法使得网络分簇情况更加均衡,节点的平均功耗更少,更合理,网络的生存时间更长。
关键词：能量有效,多跳,无线传感器网络,拓扑控制,仿真
参考文献
[1]孙利民,李建中,陈渝等.无线传感器[C].网络清华大学出版社,2005.5,89.107.
[2]乔俊峰,刘三阳,曹祥宇.无线传感器网络中基于节点密度的簇算法[J].计算机科学,2009,36(12):46-49.
[3]Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless micro-sensor networks[C].Proceedings of t he33rd Annual Hawaii International Confer-ence on System Sciences,Maui,2007.3005-30l4.
[4]郝晓辰,翟明,刘彬,张增仁.负载均衡的无线传感器网络拓扑控制算法[J].计算机工程,2009,35(05):84-86.
[5]汤强.无线传感器网络层次拓扑控制算法研究.华中科技大学博士学位论文.2010.6.1.
多跳路由算法 篇6
盲源分离 ( blind sources separation, BSS) 在20世纪90年代得到了长足的发展, 目前已成为现代信号处理学界的一个热点问题, 广泛应用于通信系统、 图像处理等多个领域［3—5］。盲源分离的方法有很多, 主要包括独立分量分析 ( independent component analysis, ICA) 、非线性主分量分析和状态空间法等［6］。随着研究的深入, 独立分量分析自适应算法以其计算简单、容易实现的优点已经成为了一种常用的盲源分离算法, 而由Cardoso提出的EASI算法［7］便是其中之一。其两个重要的技术指标是收敛速度和稳定性能, 受到算法中迭代步长的直接影响, 于是找到一种步长最优化的算法成为了EAS算法的研究难点。文献[8]定性的分析了固定步长的EASI算法对盲源信号分离的有效性, 结合模拟退火策略, 提出让步长在初期快速下降, 在后期精确收敛的方案; 文献[9]基于最速下降法的思想, 提出了一种步长最优化的EASI算法, 主要改善了算法的收敛速度; 文献[10]将信号分离状态的概念运用到了步长的调整上, 由信号的分离程度决定步长的学习速率。
基于上述分析, 在深入研究跳频通信及EAS算法的基础上, 采用了一种变步长的EASI算法来分离混叠在一起的跳频信号。利用串音误差值来调节EASI算法中的步长, 更好地解决了算法收敛速度和稳定性能之间的矛盾, 使其能够通过算法得到最优的解混矩阵, 从而获得对源信号的最佳估计。
1数学模型
1. 1跳频通信系统模型
mi (t) 表示第i个发射机的信息数据信号;信号载波P为信号功率, ωij和φij分别表示发射信号的频率和相位。跳频系统的第i个发射信号为
不失一般性, 跳频接收机接收到的信号由于接收天线阵列的原因, 存在加权重叠, 且被噪声污染, 则接收机接收到的信号为
式 ( 2) 中U表示在同一宽带信道中, 接收到的跳频信号数目; gi表示阵列天线在第i个信源到达方向上的方向增益; n ( t) 表示高斯白噪声。
1. 2盲源分离模型
盲源分离的定义是在源信号和传输通道特性均未知的情况下, 以不丢失源信号的信息为前提, 仅由观测信号估计出各个分量的过程, 其关键技术在于对分离矩阵的学习算法的研究。
盲源分离的数学模型如下
用混合方阵描述如下X ( t) = AS ( t) 。其中, S ( t) = [S1 ( t) , S2 ( t) …, Sn ( t) ]T是由n个未知源信号Si ( t) ( i = 1, 2, …, n) 构成的列向量, X ( t) = [X1 ( t) , X2 ( t) , …, XM ( t) ]T是由M个可观测向量Xi ( t) ( i = 1, 2, …, M) 构成的列向量, A为一个M × n的混合矩阵。
为了在混合矩阵A和源信号S ( t) 均未知的情况下, 尽可能真实的分离出源信号S ( t) , 需构建一个分离矩阵W, 使得X ( t) 经过分离矩阵W变换后得到对源信号的估计, 即y ( t) = Wx ( t) , 其中y ( t) = [y1 ( t) , y2 ( t) , …, yM ( t) ]T为输出向量, y ( t) 是源信号S ( t) 的估计。
通过上述分析, 跳频通信系统的模型和盲源分离模型在形式上具有一致性。
2基于独立分量分析的EASI算法
2. 1独立分量分析
独立分量分析是20世纪末发展起来的一种新的信号处理方法, 利用各个源信号之间的相互独立性及高阶统计量, 将已知的观测信号分解成若干个相互统计独立的分量, 算法稳健且适用范围广［11］。 芬兰学者Hyvarinena等人将独立分量分析方法归结表述为: 独立分量分析算法= 目标函数+ 优化算法。
目标函数给定后, 就可以采取经典的优化算法最优化目标函数。常用的目标函数有: 互信息最小化目标函数、负熵最大化目标函数、最大似然目标函数、自然梯度盲处理方法的目标函数。
2. 1. 1自然梯度学习算法
在自然梯度算法中, 引入目标函数—损失函数 ρ ( y, W) , 并将其数学期望R ( W) = E[ρ ( y, W) ]作为该算法的代价函数, 即输出信号y之间相互独立性的测度。将随机梯度搜索寻优的思想运用到独立分量分析, 得到随机梯度下降参数调节公式［12］:
逐项微分计算可得
式 ( 4) 中f ( y) = [f1 ( y1) , …, fN ( yN) ]T为列向量[非线性激活函数f ( y) 是自然梯度算法的关键], 它的第i个分量为
式 ( 5) 中qi ( yi) 为源信号si的近似概率密度函数。 Amari等人为权矩阵W的度量空间引入了自然黎曼度量, 并证明了在黎曼空间中参数W的最陡下降方向为黎曼梯度而非常规随机梯度, 即
从而得到自然梯度学习算法:
2. 2 EASI算法
J. F Cardoso在自然梯度目标函数基础上, 将白化算法和盲源分离算法结合在一起, 便得到了基于独立性的等变自适应分离 ( EASI) 算法, 其等变化特性即该算法不受混合矩阵和分离矩阵初始值的影响。它对算法公式不断地进行迭代修正, 从而得到正交的分离矩阵, 以达到更好的分离效果［13］。
设所有源信号为均值为0, 方差为1的随机变量, 即等价于源信号的自相关矩阵为单位矩阵
V为白化矩阵, 则有
式 ( 9) 中C = WVA。白化以后的观测矩阵, 有Ry= I, 进而对如下的代价函数进行优化, 即可实现混合信号的白化。
式 (10) 中是矩阵的2-范数。当且仅当Ry=I时得到ρW (C) =0, 由‖A‖F=tr (AAT) , 且Ry=CCT, 有
由式 ( 11) 可得
结合信息论知识, 有
式中, H ( s) 与C和y均无关, 则利用输出信号的互信息最小化准则, 有代价函数
显然, 此时的C为正交矩阵, 所以C－1= CT, 则
则关于矩阵C的迭代算法如下:
初始化C (0) =I。
由于!ρ (C, y) ≠-!ρ (C, y) T, 因此算法用[!ρ (C, y) -!ρ (C, y) T]/2来代替!ρ (C, y) , 有C (t+1) =C (t) +μ (t) {E{y (t) fT[y (t) ]-
为了保证观测信号X是白化的, 此处添加一个约束条件, 根据白化方法, 有式 (19)
即
等式两端同时右乘 (QA) -1, 则
本文中采用EASI算法的归一化迭代公式, 得到:
式 ( 22) 中非线性函数的选取取决于信号的峭度。 当信号的峭度小于0 ( 亚高斯信号) 时, f ( yi) = yi3; 当信号的峭度大于0 ( 超高斯信号) 时, f ( yi) = tanh ( yi) 。其中, tanh ( * ) 为双曲正切函数。
3基于串音误差的指数变步长EASI算法
由前两节中对EASI算法的分析可知, 算法中步长参数的作用是在每一次的迭代过程中, 控制分离矩阵W中各个元素更新的幅度, 如何合理的选择步长, 直接影响此算法的性能好坏。采用固定步长的盲源分离算法会造成收敛速度慢或者导致分离算法较差的稳定性, 即若选取较大的步长, 则算法收敛速度较快, 但是分离信号的稳定性能差, 甚至达不到分离的效果; 而若采用小的步长, 则算法的稳定性能好, 但收敛速度明显减慢。因此, 固定步长的EASI算法不能兼顾收敛速度和稳定性能的要求, 鉴于这一点, 不少学者提出对步长进行自适应变化的处理, 增加步长到一个大的稳定值以达到最快的收敛, 当进入最佳收敛点的领域时, 则相应的减少步长以提高算法的稳定性能, 由此来达到收敛速度和稳态性能的最佳平衡点。
为衡量所求得的分离矩阵W的性能优劣, 定义串音误差 ( ECT) 为
式 ( 23) 中, Gk ( i, j) 为全局变量G = WA的第i行第j列的元素。
文中采用的是基于串音误差变化的步长, 称之为指数变步长EASI算法, 公式为
式 ( 24) 中参数 α > 0控制算法的收敛速度, 参数β > 0控制算法到达收敛时的稳定性能。由公式可知, 这种变步长具有很好的调整能力, 步长参数可以自适应地在收敛速度和稳定性能之间调整, 当ECT的值很大的时候, 变步长取值较大, 从而收敛速度较快; 而当ECT达到一个较小值时, 说明分离效果已经较好, 步长取较小值, 从而提高算法的稳定性, 以达到收敛速度和稳定性能的最佳结合点。实际应用中, 根据分离效果的需要适当地选择参数 α、β 的值。
指数变步长的具体实现步骤如下:
( 1) 对观测信号进行预处理, 包括中心化和白化, 从而获得白化数据矩阵Z。
( 2) 设置初始分离矩阵W, 并选择合适的初始步长 μ ( k) 。
( 3) 计算Y = WZ。
( 4) 根据公式, 求解步长 μ ( k + 1) 。
( 5) 更新分离矩阵W ( k + 1) , 若未收敛, 返回步骤 ( 3) ; 若收敛, 则算法结束。
4计算机仿真及性能比较
4. 1仿真实验一
运用改进后的EASI算法进行多跳频信号的盲源分离, 实验中采用的源信号为两组跳频信号及一组噪声信号, 其中两组跳频信号的采样频率同为1 000 Hz, 且第二组跳频信号的跳速为第一组的2倍, 取信号的前900个采样点作为实验样本。仿真时, 跳频信号及噪声通过计算机产生的随机混合矩阵进行混合。
经过分离后, 得到分离矩阵为
比较图3和图5, 可以看出, 除了排序、幅值和相位的差别外, 分离信号很好的逼近了源信号。而跳频信号的排序、幅值及相位的改变对信号的识别及参数估计并无影响; 同时可见, 该算法能将跳频信号和噪声分离开, 说明了算法的实践性。所以通过实验证明, 基于串音误差的变步长EASI算法能有效地分离多跳频信号。
4. 2仿真实验二
用固定步长的EASI算法与改进后的指数变步长算法分别对实验一中的多跳频信号进行盲源分离实验, 并对其性能指标PI ( performance index) , 即串音误差, 定义式见公式 ( 23) , 对两种方法进行比较。 设置两种算法的初始步长均为0. 005, 即固定步长为0. 005, 指数变步长算法的参数分别设置为 α = 0. 2, β = 0. 001。
当源信号达到最佳分离状态时, PI值应为零, 但在实际应用中, 由于计算机仿真存在误差, 导致PI值无法直接等于零, 而是逐渐趋近于零。
从图6可见, 指数变步长算法在迭代10 000次的时候已经趋近于零, 而固定步长算法在迭代15 000次之后依然不能稳定地达到理想状态。通过实验证明, 改进后的指数变步长EASI算法在收敛速度和稳定性上都比固定步长有较大的改善, 说明了算法的可行性。
5总结