论文部分内容阅读
Ad Hoc网络是由移动节点构成的，不依赖于任何固定基础设施的无线网络。在能量有限的移动自组网中，节点剩余电池能量是在选择路由时应考虑的重要指数，已成为Ad Hoc网络路由协议的一个研究热点。对于节点能量的限制方面，如果使用多路径方式分发报文，那么节点电池将以比较接近的速率消耗，这使得整个网络的生命周期增长[1,2]。如果在协议设计的时候，就尽量减少控制报文，那么随着节点移动性的增加，协议往往有着更优异的表现。
蜜蜂的很多行为特性和Ad Hoc是十分相似的。文献[3,4]中提出的原理组成了蜜蜂路由协议的基础。本文介绍一种蜜蜂路由协议（Bee Routing Protocol, BRP），使用了很少的路由控制报文，在保持常规性能与现有的路由近似的同时，与现在已经提出的路由协议相比，消耗更少的能量，提高能量效率。在报文传送率和延时方面，与AODV和DSDV近似，而在能量消耗方面，则有着明显的优势。
1 基于蜜蜂觅食原理的移动代理模型
针对Ad Hoc路由的第一个协议是基于蚂蚁群居行为原理的路由协议(ARA)，该协议是受到了蚂蚁群居行为的启发，节点以按需的方式发布蚂蚁代理，从而限制其引起的负载。最近在固定网络中提出的一种蜜蜂路由算法，可达到和蚂蚁路由相似或者更好的性能。蜜蜂路由算法也是受自然界中的蜜蜂觅食行为启发产生的一种具有自适应特性的分布式算法。蜜蜂代理模型也可以称为基于生物群体智能的移动代理模型，由包装者、侦察者、觅食者和蜂群等四类代理组成，模型中使用了一种增强学习的技术。
包装者：模仿蜜蜂存储食物的工作，始终在节点内部接收和存储来自于传输层的数据报文。包装者为数据报文发现觅食者，当把数据报文移交给觅食者后死亡。
侦察者：负责寻找从源节点到目的节点的路由。每个侦察者由ID和源节点的唯一密钥来标识。一旦侦察者到达目的节点，它将按原路返回。目的节点将遣回所有接收到的侦察者，使得可以发现多重路由。一旦侦察者返回到源节点，那么将用舞蹈来征召觅食者按其发现的路由行动。舞蹈可以描述侦察者通过的路由信息。
觅食者：从其它觅食者那里接收数据报文，然后向目的节点转发。在到达目的节点之前，觅食者以点到点的方式传输报文，并且收集与其类型相对应的网络信息。一旦觅食者到达目的节点，当目的节点往源节点发送信息的时候，觅食者将顺带返回源节点，否则它将一直停留在原处。这样的优化减少了控制报文的负载，因此节省了能量。觅食者返回源节点后，那么它将按侦察者的舞蹈方式将其所收集的信息通知随后的觅食者。
蜂群：用来解决源节点可能用尽所有的觅食者而无法进行通信的问题。当a节点对于b节点的觅食者进出差达到某一门限值的时候，节点a发起蜂群到节点b。其中设置一个觅食者在蜂群的头部，而其它的放在蜂群的有效载荷中。一旦蜂群到达节点b，从有效载荷中解析出觅食者，并按正常的接收方式存储。
2 蜜蜂路由协议的体系结构
BRP的体系结构如下图所示。
2.1包装层功能
包装层是到传输层的接口，可以与舞蹈层和入口进行通信。如果收到来自传输层的数据报文，包装层将产生一个包装者来存储数据报文。包装者将为数据报文从舞蹈层选择一个合适的觅食者。如果找到觅食者后，将把数据报文移交给觅食者，包装者死亡。否则，需要等待觅食者返回，如果超过规定时间还未出现觅食者，它将发送侦察者来寻找到达目的节点的新路由。对于从入口接收到的报文，包装层处理的过程与处理传输层的报文的过程十分相似。因为侦察者不一定能找到目的节点，不可能一直存在于网络中，在发送侦察者之前，必须设置侦察者的TTL（表示报文应该被重新广播的次数）和ID，并启动计时器。其中TTL和ID是用于判断侦察者是应被接收还是丢弃，而计时器则是帮助该侦察者的源节点判断是否需要发送新的侦察者，每个新的侦察者都拥有不同的ID号。在此，可以将序列号的思想引入到ID的命名中，ID号可以看成是一个单调增的序列。这样可以使得节点不用保存所有收到的侦察者的ID，大大地减小了存储负载。
2.2舞蹈层功能
舞蹈层是蜂房的核心，在路由抉择中扮演了重要的角色。当觅食者返回后，通过舞蹈反映经过路径的质量，并征召新的觅食者出发。但是，每个觅食者的质量参数有所不同。如果路径中节点有足够的剩余能量，或者即使路径中有的节点的能量已经不足，但仍有大量的包装者在等待，允许使用更多的觅食者。如果没有包装者在等待，那么有较优路径的觅食者也不会跳舞。这将帮助调节路由中觅食者的数量。
当包装者向觅食者发送请求的时候，舞蹈层发送匹配的觅食者到包装层。匹配功能中将不考虑已经过期的觅食者。如果多个觅食者匹配，则随机选择一个觅食者。这将帮助在多路由中分发报文，避免拥塞，并使得各个节点的能量消耗速度近似。被选择的觅食者的克隆被发往包装层，而原始的觅食者在减少其舞蹈次数后被存储在舞蹈层。如果跳舞次数为0，原始的觅食者被发送到包装层，并在舞蹈层删除其对应的记录。使用上面提到的原理，拥有最新路由信息的觅食者，最有可能保持有效。如果到目的节点的最后的觅食者都离开蜂房了，那么蜂房就没有到达目的节点的路由。如果存在到目的节点的路由，那么觅食者将很快会返回，而如果在规定时间内都没有觅食者返回，那么认为丢失了到目的节点的路由。这种机制消除了定期的hello报文和路由报错报文，减小了路由负载，因而能量的消耗也相应地减少了。
2.3入口功能
入口是到MAC（Medium Access Control）层的接口，也可以与包装层通信，但却不能和舞蹈层直接通信。入口处理所有报文的进出。在TTL未过期并且还未达到目的节点之前，侦察者在入口被接收和广播。侦察者和源节点的ID被存储在本地的信息表中。入口将会对收到的每一个侦察者做检查，如果之前已经接收到了来自于某节点的侦察者，以后再次收到该侦察者时将不会接受它。如果接收节点是侦察者的目的节点，那么修改侦察者的下一跳信息，并按原路径返回。如果觅食者和存在于舞蹈层的侦察者有相同的目的节点，那么将侦察者的路由添加到觅食者中。如果现在的节点是觅食者的目的节点，那么将转发到包装层，其它的直接转发到下一跳节点的MAC接口。
3 蜜蜂算法的仿真实验
3.1实验环境及评价指标
操作系统是Windows 2000下Cygwin平台，网络仿真平台是ns2.28。仿真中，节点总数设置为30个，节点运动范围为2400m × 800m。网络中节点的运动方式采用随机运动模型， MAC层使用802.11协议，节点传输半径为100m，链路带宽为2Mbps，模拟时间为200s。在仿真实验中，通过使用能量消耗、报文传送率、延时、网络寿命等测量指标来评价路由性能，使用文献[5,6]中的模型来评估广播或者点到点传输的能量消耗。
3.2 算法表现比较
研究算法的表现是仿真实验的目的。提高节点速度将降低网络的稳定性。提高速度节点的位置相对更不稳定，出现丢包的几率也更大。BRP、DSDV、AODV报文传送率都有所降低，但前两种协议的报文传送率比较接近，都明显高于AODV，但BRP和AODV的延时是比较接近的，都明显大于DSDV。由于BRP在选取路由方面更为灵活，并且既在不同的路径上传输报文，也在最优的路径上传输报文，所以在能量消耗方面，表现最为出色。由于节点高速移动时可以选取多条通往目的节点的路径，报文将通过更多不同节点，使得BRP随着节点移动速度的提高有着更长的网络生命周期。后两种协议随着节点速度的提高，控制报文的数量显著增长，电池能量消耗很快。
3.3 拥塞比较
拥塞的定义至今无法完全统一。通过仿真实验验证拥塞控制研究的思路，目前也没有统一的规范和评价标准。本文选择节点的速度在0-30m/s之间，报文发送速率选择10、30、50和70个/s逐渐增加，其它参数不变。随着负载的增加，BRP、DSDV、AODV三种协议都能正常运行，但在报文传送率方面，DSDV表现最差，在延时方面AODV所需最长。在统计仿真结果的时候，如果报文没有传送到目的节点，那么并未将其所用的时间计算在平均延时中，因为DSDV作为先应式路由协议，不需要发起路由查询，所以延时要小于后应式路由。当负载增加的时候，信道的冲突使丢弃的报文将越来越多，而被丢弃的报文并不增大延时，反而使得源节点可能找到更快的路径到达目的节点，所以平均延时减小。比较而言，BRP的能量消耗是最小的，其次是DSDV，AODV对能量的消耗则是最大的。
4 结束语
本文介绍的一种新的、基于蜜蜂代理的路由协议BRP，主要依靠侦察者和觅食者两类代理。其中侦察者主要负责按时地发现到达目的节点的路由，而觅食者主要负责传输数据报文和评估路由的质量。觅食者试图优化采蜜的能量效率，而且在没有任何环境信息的情况下，觅食者也可以作出决定，得到的路由评估结果用于以后选路的参考，如此可以减少控制报文的数量，从而节约能源。仿真实验表明，BRP在能量消耗方面的优势很明显。
参考文献
[1]Suresh S, Mike W. Raghavendra. Power-aware Routing in Mobile Ad Hoc Networks[C] //Proceeding of the Fourth ACM/IEEE Conference on Mobile Computing and Networking (MobiCom),Dallas,USA:IEEE Press,1998:181-190.
[2]Christine E, Krishna M, Prathima A, and Jyh-Cheng C. A Survey of Energy Efficient Network Protocols for Wireless Networks[J].Wireless Networks,2001,7(4): 343-358.
[3]K. von Frisch. The Dance Language and Orientation of Bees [J]. Harvard University Press, Cambridge,1967: 566-572.
[4]T.D. Seeley. The Wisdom of the Hive. Harvard University Press,London,1995.
[5]Laura F and Martin N. Investigating the Energy Consumption of a Wireless Network Interface in an Ad Hoc Networking Environment[C]. //Proceeding of IEEE INFOCOM 2001, Anchorage AK,US,2001:548-1557.
[6]Josh B, David A. A Performance Comparison of Multi-hop Wireless Ad Hoc Network Routing Protocols[C]. //Proceeding of Fourth ACM/IEEE Conference on Mobile Computing and Networking (MobiCom), Dallas, TX: IEEE Press,1998: 85-97.
蜜蜂的很多行为特性和Ad Hoc是十分相似的。文献[3,4]中提出的原理组成了蜜蜂路由协议的基础。本文介绍一种蜜蜂路由协议（Bee Routing Protocol, BRP），使用了很少的路由控制报文，在保持常规性能与现有的路由近似的同时，与现在已经提出的路由协议相比，消耗更少的能量，提高能量效率。在报文传送率和延时方面，与AODV和DSDV近似，而在能量消耗方面，则有着明显的优势。
1 基于蜜蜂觅食原理的移动代理模型
针对Ad Hoc路由的第一个协议是基于蚂蚁群居行为原理的路由协议(ARA)，该协议是受到了蚂蚁群居行为的启发，节点以按需的方式发布蚂蚁代理，从而限制其引起的负载。最近在固定网络中提出的一种蜜蜂路由算法，可达到和蚂蚁路由相似或者更好的性能。蜜蜂路由算法也是受自然界中的蜜蜂觅食行为启发产生的一种具有自适应特性的分布式算法。蜜蜂代理模型也可以称为基于生物群体智能的移动代理模型，由包装者、侦察者、觅食者和蜂群等四类代理组成，模型中使用了一种增强学习的技术。
包装者：模仿蜜蜂存储食物的工作，始终在节点内部接收和存储来自于传输层的数据报文。包装者为数据报文发现觅食者，当把数据报文移交给觅食者后死亡。
侦察者：负责寻找从源节点到目的节点的路由。每个侦察者由ID和源节点的唯一密钥来标识。一旦侦察者到达目的节点，它将按原路返回。目的节点将遣回所有接收到的侦察者，使得可以发现多重路由。一旦侦察者返回到源节点，那么将用舞蹈来征召觅食者按其发现的路由行动。舞蹈可以描述侦察者通过的路由信息。
觅食者：从其它觅食者那里接收数据报文，然后向目的节点转发。在到达目的节点之前，觅食者以点到点的方式传输报文，并且收集与其类型相对应的网络信息。一旦觅食者到达目的节点，当目的节点往源节点发送信息的时候，觅食者将顺带返回源节点，否则它将一直停留在原处。这样的优化减少了控制报文的负载，因此节省了能量。觅食者返回源节点后，那么它将按侦察者的舞蹈方式将其所收集的信息通知随后的觅食者。
蜂群：用来解决源节点可能用尽所有的觅食者而无法进行通信的问题。当a节点对于b节点的觅食者进出差达到某一门限值的时候，节点a发起蜂群到节点b。其中设置一个觅食者在蜂群的头部，而其它的放在蜂群的有效载荷中。一旦蜂群到达节点b，从有效载荷中解析出觅食者，并按正常的接收方式存储。
2 蜜蜂路由协议的体系结构
BRP的体系结构如下图所示。
2.1包装层功能
包装层是到传输层的接口，可以与舞蹈层和入口进行通信。如果收到来自传输层的数据报文，包装层将产生一个包装者来存储数据报文。包装者将为数据报文从舞蹈层选择一个合适的觅食者。如果找到觅食者后，将把数据报文移交给觅食者，包装者死亡。否则，需要等待觅食者返回，如果超过规定时间还未出现觅食者，它将发送侦察者来寻找到达目的节点的新路由。对于从入口接收到的报文，包装层处理的过程与处理传输层的报文的过程十分相似。因为侦察者不一定能找到目的节点，不可能一直存在于网络中，在发送侦察者之前，必须设置侦察者的TTL（表示报文应该被重新广播的次数）和ID，并启动计时器。其中TTL和ID是用于判断侦察者是应被接收还是丢弃，而计时器则是帮助该侦察者的源节点判断是否需要发送新的侦察者，每个新的侦察者都拥有不同的ID号。在此，可以将序列号的思想引入到ID的命名中，ID号可以看成是一个单调增的序列。这样可以使得节点不用保存所有收到的侦察者的ID，大大地减小了存储负载。
2.2舞蹈层功能
舞蹈层是蜂房的核心，在路由抉择中扮演了重要的角色。当觅食者返回后，通过舞蹈反映经过路径的质量，并征召新的觅食者出发。但是，每个觅食者的质量参数有所不同。如果路径中节点有足够的剩余能量，或者即使路径中有的节点的能量已经不足，但仍有大量的包装者在等待，允许使用更多的觅食者。如果没有包装者在等待，那么有较优路径的觅食者也不会跳舞。这将帮助调节路由中觅食者的数量。
当包装者向觅食者发送请求的时候，舞蹈层发送匹配的觅食者到包装层。匹配功能中将不考虑已经过期的觅食者。如果多个觅食者匹配，则随机选择一个觅食者。这将帮助在多路由中分发报文，避免拥塞，并使得各个节点的能量消耗速度近似。被选择的觅食者的克隆被发往包装层，而原始的觅食者在减少其舞蹈次数后被存储在舞蹈层。如果跳舞次数为0，原始的觅食者被发送到包装层，并在舞蹈层删除其对应的记录。使用上面提到的原理，拥有最新路由信息的觅食者，最有可能保持有效。如果到目的节点的最后的觅食者都离开蜂房了，那么蜂房就没有到达目的节点的路由。如果存在到目的节点的路由，那么觅食者将很快会返回，而如果在规定时间内都没有觅食者返回，那么认为丢失了到目的节点的路由。这种机制消除了定期的hello报文和路由报错报文，减小了路由负载，因而能量的消耗也相应地减少了。
2.3入口功能
入口是到MAC（Medium Access Control）层的接口，也可以与包装层通信，但却不能和舞蹈层直接通信。入口处理所有报文的进出。在TTL未过期并且还未达到目的节点之前，侦察者在入口被接收和广播。侦察者和源节点的ID被存储在本地的信息表中。入口将会对收到的每一个侦察者做检查，如果之前已经接收到了来自于某节点的侦察者，以后再次收到该侦察者时将不会接受它。如果接收节点是侦察者的目的节点，那么修改侦察者的下一跳信息，并按原路径返回。如果觅食者和存在于舞蹈层的侦察者有相同的目的节点，那么将侦察者的路由添加到觅食者中。如果现在的节点是觅食者的目的节点，那么将转发到包装层，其它的直接转发到下一跳节点的MAC接口。
3 蜜蜂算法的仿真实验
3.1实验环境及评价指标
操作系统是Windows 2000下Cygwin平台，网络仿真平台是ns2.28。仿真中，节点总数设置为30个，节点运动范围为2400m × 800m。网络中节点的运动方式采用随机运动模型， MAC层使用802.11协议，节点传输半径为100m，链路带宽为2Mbps，模拟时间为200s。在仿真实验中，通过使用能量消耗、报文传送率、延时、网络寿命等测量指标来评价路由性能，使用文献[5,6]中的模型来评估广播或者点到点传输的能量消耗。
3.2 算法表现比较
研究算法的表现是仿真实验的目的。提高节点速度将降低网络的稳定性。提高速度节点的位置相对更不稳定，出现丢包的几率也更大。BRP、DSDV、AODV报文传送率都有所降低，但前两种协议的报文传送率比较接近，都明显高于AODV，但BRP和AODV的延时是比较接近的，都明显大于DSDV。由于BRP在选取路由方面更为灵活，并且既在不同的路径上传输报文，也在最优的路径上传输报文，所以在能量消耗方面，表现最为出色。由于节点高速移动时可以选取多条通往目的节点的路径，报文将通过更多不同节点，使得BRP随着节点移动速度的提高有着更长的网络生命周期。后两种协议随着节点速度的提高，控制报文的数量显著增长，电池能量消耗很快。
3.3 拥塞比较
拥塞的定义至今无法完全统一。通过仿真实验验证拥塞控制研究的思路，目前也没有统一的规范和评价标准。本文选择节点的速度在0-30m/s之间，报文发送速率选择10、30、50和70个/s逐渐增加，其它参数不变。随着负载的增加，BRP、DSDV、AODV三种协议都能正常运行，但在报文传送率方面，DSDV表现最差，在延时方面AODV所需最长。在统计仿真结果的时候，如果报文没有传送到目的节点，那么并未将其所用的时间计算在平均延时中，因为DSDV作为先应式路由协议，不需要发起路由查询，所以延时要小于后应式路由。当负载增加的时候，信道的冲突使丢弃的报文将越来越多，而被丢弃的报文并不增大延时，反而使得源节点可能找到更快的路径到达目的节点，所以平均延时减小。比较而言，BRP的能量消耗是最小的，其次是DSDV，AODV对能量的消耗则是最大的。
4 结束语
本文介绍的一种新的、基于蜜蜂代理的路由协议BRP，主要依靠侦察者和觅食者两类代理。其中侦察者主要负责按时地发现到达目的节点的路由，而觅食者主要负责传输数据报文和评估路由的质量。觅食者试图优化采蜜的能量效率，而且在没有任何环境信息的情况下，觅食者也可以作出决定，得到的路由评估结果用于以后选路的参考，如此可以减少控制报文的数量，从而节约能源。仿真实验表明，BRP在能量消耗方面的优势很明显。
参考文献
[1]Suresh S, Mike W. Raghavendra. Power-aware Routing in Mobile Ad Hoc Networks[C] //Proceeding of the Fourth ACM/IEEE Conference on Mobile Computing and Networking (MobiCom),Dallas,USA:IEEE Press,1998:181-190.
[2]Christine E, Krishna M, Prathima A, and Jyh-Cheng C. A Survey of Energy Efficient Network Protocols for Wireless Networks[J].Wireless Networks,2001,7(4): 343-358.
[3]K. von Frisch. The Dance Language and Orientation of Bees [J]. Harvard University Press, Cambridge,1967: 566-572.
[4]T.D. Seeley. The Wisdom of the Hive. Harvard University Press,London,1995.
[5]Laura F and Martin N. Investigating the Energy Consumption of a Wireless Network Interface in an Ad Hoc Networking Environment[C]. //Proceeding of IEEE INFOCOM 2001, Anchorage AK,US,2001:548-1557.
[6]Josh B, David A. A Performance Comparison of Multi-hop Wireless Ad Hoc Network Routing Protocols[C]. //Proceeding of Fourth ACM/IEEE Conference on Mobile Computing and Networking (MobiCom), Dallas, TX: IEEE Press,1998: 85-97.