针对延迟容忍网络(DTN)中喷雾等待(SaW)路由协议在转发消息时选择中继节点的盲目性, 提出一种基于节点效用的路由协议SaW-Utility.此路由协议在转发消息时, 将根据节点剩余缓存和节点交付概率等因素选择中继节点, 从而减少中继节点选择的盲目性.仿真结果表明, 相比于SaW路由协议, SaW-Utility路由协议明显提高了消息转发成功率, 降低了网络开销.
Spray and wait (SaW) routing protocols select relay node arbitrarily in message forwarding process. Aiming at the arbitrariness, a new routing protocol, SaW-Utility, is proposed based on the utility of nodes. When messages are forwarded, SaW-Utility selects relay nodes according to the utility of nodes, such as the sizes of remaining buffer, success rate of message delivery, and etc., so that the arbitrariness can be overcome. The simulation results show that the proposed routing protocol significantly improves the success rate of message forwarding and reduces network overhead compared with SaW routing protocols.
针对现有网络无法实现星际网络等高延迟通信，延迟容忍网络(DTN, delay tolerant network)研究组首先提出了DTN概念[1]. DTN具有连通间歇性、高延迟、高错误率、低传输率、可能不存在端到端的连接通路等特点，其应用领域比较广泛，如星际网络通信、野生动物追踪、偏远地区网络通信、车载网络交互等.
DTN的特点决定其无法应用传统移动网络和有线网络的路由协议，因此路由协议成为DTN研究的重点.目前，DTN路由协议还存在很多不足，其在转发消息时，没有进行节点选择而直接进行消息转发，消息转发成功的概率较低并且网络开销较大.鉴于DTN广泛的应用领域以及路由协议研究对其的重要性，对DTN路由协议进行研究及改进以提高网络的传输性能显得尤为重要.
1 相关工作喷雾等待(SaW, spray and wait)路由协议[2]在转发消息时分为2个阶段：“喷雾阶段”和“等待阶段”.在喷雾阶段，消息源节点向网络中喷雾固定数量的消息.在消息源节点仅剩一个消息时，进入等待阶段，在此阶段只有遇到消息的目的节点才进行消息转发.
如今，国内外已提出很多对SaW路由协议的改进方案，主要分为2类：基于节点特点的改进和基于节点相遇信息的改进.
1) 基于节点特点的改进.将节点的剩余缓存与移动速度相结合，作为中继节点选择的依据，当2个节点相遇并建立连接后，依据2个节点的移动速度及剩余缓存大小来选择消息转发中继节点[3].每个节点都具有能量，根据节点能量的大小来分配消息副本，其中能量较大的节点可得到较多的消息副本，而能量较小的节点得到较少的消息副本[4].
2) 基于节点相遇信息的改进.在DTN中，主要依靠节点的移动转发消息.节点在移动时相遇其他节点，会产生很多相遇信息[5].据此相遇信息，可以预测它们再次相遇的概率[6]和投递概率，并根据相应的配额分配策略进行消息投递，从而提高消息的转发成功率[7].
综上所述，目前对SaW已做了一定的改进，并在消息转发成功率方面取得了良好效果.但是现有方法没有对节点的交付概率(节点转发出去的消息总数与此节点收到的总消息数的比值)进行判断，可能造成将消息转发至恶意节点，引起消息被随意丢弃等问题.利用节点交付概率可以度量节点活跃度以及节点是否存在任意丢包行为.因此，笔者结合节点剩余缓存和节点交付概率，提出了一种基于节点效用的路由协议SaW-Utility，并与经典SaW进行了实验对比.实验结果表明，所提出的方案在消息转发成功率、网络开销等方面具有更高的有效性.
2 SaW-Utility2.1 SaW-Utility路由协议算法思想经典SaW路由协议能很好地提高消息的转发成功率，但该协议存在一定不足：在“喷雾阶段”转发消息时不进行节点选择，在遇到其他节点时直接进行转发，不考虑节点自身的性能.如果遇到的节点不是活跃节点，可能降低消息的转发成功率，增大网络开销，从而降低网络的传输性能.
笔者在原路由协议优点(有限的消息复制、适用于有限缓存的场景)基础上，提出了基于节点效用的路由协议SaW-Utility.其采用“节点剩余缓存+节点交付概率”作为中继节点选择的依据，主要改进体现在：在其喷雾阶段，采用二元喷雾的方式，基于节点效用(拥有比较大的剩余缓存和节点交付概率)进行消息转发.当中继节点的效用值大于消息携带节点时，才将消息转发至该节点，否则不进行转发.在喷雾阶段完成之后，即固定数量消息喷雾完成，进入等待阶段，等待目的节点的出现.
在网络中，每个节点都有其相应的效用值，将节点剩余缓存与节点交付概率进行归一化处理，得到节点效用值的计算方法为
|
其中：pro_buff、freebuff、buffsize分别代表基于节点剩余缓存的权重、节点剩余缓存、节点总缓存；pro_delivery、deliverycount、count分别代表基于节点交付概率的权重、节点转发的消息数、节点收到的总消息数，并且有pro_buff+pro_delivery=1.
2.2 SaW-Utility路由协议描述1) 建立连接的节点i没有消息或者当前正在传送消息，结束.
2) 所选择的消息的目的节点是消息所在节点的所有连接中的一个，直接将消息转发给目的节点.
3) 得到节点i还有副本需要喷洒的消息列表，将其按照随机模式，并赋值给新的消息列表List〈Message〉 copiesLeft.
4) 节点j是节点i某一时刻所有连接中的一个，如果节点i还有消息副本需要喷洒，即copiesLeft. size > 0，则计算节点j的效用值utilityj，与节点i的效用值utilityi进行比较，如果utilityj > =utilityi，将节点j加入“消息-连接”对应表L中，所以L中存有的所有节点的效用值都大于或等于节点i的效用值.如果此时刻节点i还有连接节点，则重复3)、4).最后对整个“消息-连接”对应表进行排序，按照此顺序依次进行消息转发.
2.3 SaW-Utility路由协议算法分析与SaW路由协议相比，SaW-Utility路由协议在转发消息时进行节点选择，这将在一定程度上增加算法的时间复杂度和空间复杂度.假设在某一时刻，建立连接的数目为n，消息需要转发的剩余副本数量是m，其中m的最大值是事先限定的消息副本数量.
在“喷雾阶段”，如果消息需要转发的剩余副本数量大于1，SaW路由协议将消息试图转发给其所有连接，而SaW-Utility路由协议将根据节点效用进行节点选择，这是引起2种路由协议时间复杂度不同的主要原因，所以只要对比消息转发时的时间复杂度和空间复杂度，就能发现两者在时间复杂度以及空间复杂度的变化.
2.2节中已给出SaW-Utility路由协议的伪代码，通过分析发现在转发消息时，SaW路由协议的时间复杂度是O(n(2+2m))；而SaW-Utility路由协议对消息列表进行排序，此时间复杂度为O(mlgm)，所以SaW-Utility路由协议的时间复杂度是O(mlgm+n(4m+3)).由于m是消息需要转发的剩余副本数量，m的最大值是事先限定的消息副本数量，为了避免网络中消息副本太多，其取值一般是一个常数，并比较小，所以影响路由协议时间复杂度的是建立连接的数目n，从而以上2种路由协议的时间复杂度都是O(n).而相比于SaW路由协议，SaW-Utility路由协议仅仅额外使用存放已选择节点的空间，比SaW路由协议多出有限的空间复杂度.
3 实验与仿真分析DTN的模拟器有很多种类，下面基于机会网络环境(ONE, opportunistic network environment)模拟器进行模拟仿真. ONE模拟器由部分赫尔辛基市地图作为网络的仿真场景，节点在此区域进行移动.仿真场景大小是4300m×3400m，包含5组节点：第1组包含80个行人节点；第2组包含40个汽车节点；第3组、第4组及第5组分别包含2个电车节点，电车的缓存是50MB，移动速度是7~10m/s.
由于参数权重变化会导致网络性能改变，需要在仿真过程中，逐渐改变2个参数的权重来找到使网络性能最好的权重比例.剩余缓存和节点交付概率的权重比例逐渐从只考虑剩余缓存改变为只考虑节点交付概率.在仿真时，共对SaW-Utility选择7组数据，剩余缓存和节点交付概率的权重比例分别为1.0:0.0、0.75:0.25、0.5:0.5、0.25:0.75、0.0:1.0，并与SaW进行对比.在进行仿真时，通过以下3个方面进行路由协议的性能分析.
消息转发成功率：成功递交给目的节点的消息个数/生成的消息总数.
网络开销：(网络中被中继的消息数量－成功递交的消息数量)/成功递交的消息数量.
平均传输延迟：所有转发成功的消息从源节点到目的节点的时间之和/总的消息个数.
3.1 随节点缓存变化的网络性能比较仿真时仅改变节点缓存，第1组及第2组节点缓存从5MB逐渐变化到35MB，仿真时间为12h.图 1为随着节点缓存的变化，SaW-Utility路由协议与SaW路由协议的网络性能比较.
|
图 1 节点缓存变化对网络性能的影响 |
由图 1(a)可知，6组仿真数据的消息转发成功率有一个共同特点就是都随着缓存的增加而不断增大，而且在节点缓存增加到20MB时，都不再明显增加，达到一个稳定值. SaW-Utility路由协议是基于节点效用进行消息转发的，并且节点效用受节点剩余缓存的影响，在节点缓存比较充足时，相比于SaW路由协议，SaW-Utility路由协议转发消息成功率就比较低.图 1(b)所示为节点缓存不断变化的网络开销的比较，观察此图可以发现SaW路由协议的网络开销略微大于SaW-Utility路由协议.这是因为SaW-Utility路由协议中继的消息数量较少，而成功递交的消息较多.图 1(c)是平均传输延迟的比较，可以看出，随着节点缓存的不断增加，SaW-Utility路由协议与SaW路由协议的平均传输延迟都不断增加，并且SaW-Utility路由协议的平均延迟要明显高于SaW路由协议.
3.2 随节点移动速度变化的网络性能比较仿真时仅改变节点移动速度，第1组(行人组)节点的移动速度从0.5m/s逐渐变化为3.0m/s，节点缓存为5MB不变，仿真时间为9h不变.
图 2为随着节点移动速度的变化，SaW-Utility路由协议与SaW路由协议的各个网络性能比较.由图 2(a)可知，SaW-Utility与SaW路由协议在2m/s时达到峰值.当SaW-Utility路由协议剩余缓存和节点交付概率的权重比是1.0:0.0、0.75:0.25、0.5:0.5、0.25:0.75时，消息转发成功率明显高于SaW路由协议.图 2(b)表明网络开销随节点移动速度的变化，当节点移动速度相同时，SaW路由协议的网络开销明显高于SaW-Utility路由协议.图 2(c)表明网络平均传输延迟随着节点移动速度的变化，当节点移动速度相同时，SaW路由协议的平均延迟较低.
|
图 2 节点移动速度变化对网络性能的影响 |
通过以上2组仿真发现，相比于SaW路由协议，SaW-Utility路由协议在提高其他网络性能的同时，却由于成功转发的消息较多及在转发时进行节点选择而具有较高平均传输延迟.针对此缺点，可以通过效用值的大小进行分配复制配额，从而使得具有更大效用值的节点获得更多的复制.
4 结束语笔者提出一种基于节点效用的路由协议SaW-Utility，是根据节点特点对经典的SaW协议进行的改进. SaW-Utility充分利用了节点剩余缓存及节点交付概率等特性来选择进行消息转发的中继节点.对SaW-Utility和SaW进行的时空复杂度分析对比发现，两者的时间复杂度都是O(n)，SaW-Utility的空间复杂度也仅仅略高于SaW.通过改变节点缓存、移动速度等仿真参数对SaW-Utility路由协议进行仿真，并与SaW进行性能比较，发现SaW-Utility明显提高了网络消息转发成功率，降低了网络开销.但是，由于SaW-Utility在转发消息时增加了节点选择过程，可能导致平均传输延迟较高.因此，降低平均传输延迟将是下一步工作的重点.
| [1] | Fall K. A delay-tolerant network architecture for challenged Internets[C]//Proc of the ACM SIGCOMM 2003. New York: ACM, 2003: 27-34. |
| [2] | Spyropoulos T, Psounis K, Raghavendra C S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks[C]//MProceedings of ACM SIGCOMM Workshops: Conference on Computer Communications. New York:[s.n.], 2005: 252-259. |
| [3] |
李家瑜, 张大方, 何施明. DTN中基于节点价值的效用路由协议[J]. 计算机应用研究, 2012, 29(9): 3380–3382.
Li Jiayu, Zhang Dafang, He Shiming. Utility routing algorithm based on value of node in DTN[J].Application Research of Computers, 2012, 29(9): 3380–3382. |
| [4] | Liu Can, Deng Su, Huang Hongbin, et al. Fair spray and wait routing in DTN[C]//2011 4th IEEE International Conference on Computer Science and Information Technology. Chengdu:[s.n.], 2011: 219-222. |
| [5] | Jung K H, Lim W S, Jeong J P, et al. A link contact duration-based routing protocol in delay-tolerant networks[J].Wireless Networks, 2013, 19(6): 1299–1316. doi: 10.1007/s11276-012-0534-0 |
| [6] |
张振京, 金志刚, 舒炎泰. 基于节点运动预测的社会性DTN高效路由[J]. 计算机学报, 2013, 36(3): 626–635.
Zhang Zhenjing, Jin Zhigang, Shu Yantai. Efficient routing in social DTN based on nodes' movement prediction[J].Chinese Journal of Computers, 2013, 36(3): 626–635. |
| [7] |
彭敏, 洪佩琳, 薛开平, 等. 基于投递概率预测的DTN高效路由[J]. 计算机学报, 2011, 34(1): 175–180.
Peng Min, Hong Peilin, Xue Kaiping, et al. Delivery probability prediction based efficient routing in DTN[J].Chinese Journal of Computers, 2011, 34(1): 175–180. |