针对延迟容忍移动传感器网络提出一种基于广播的副本消除数据传输机制（CRD）.CRD机制中，传感器节点利用基站在频率f1上的大功率广播信息完成自身转发概率的计算和冗余消息副本的清理，基于转发概率在频率f2上完成节点间的消息转发.同时，CRD采用消息生存时间和消息转发域值M来完成消息队列的管理.仿真结果表明，与其他数据传输机制相比，CRD能达到传输成功率、传输延迟和通信开销的有效平衡.
Proposed a broadcasting-based copy-removed data delivery scheme (CRD) for delay tolerant mobile sensor networks (DTMSN). Using broadcasting information of base station on the frequency of f1, sensor nodes not only can remove the redundant messages, but also can compute their own motion states and delivery probabilities which provide the basis for messages forwarding between sensor nodes on the frequency of f2. At the same time, CRD employs the message survival time and message forwarding domain M to manage the message queues. Simulation results show that CRD has a higher message delivery ratio and less data delivery delay than many other DTMSN data delivering approaches.
延迟容忍移动传感器网络(DTMSN，delay tolerant mobile sensor networks)通常采用“存储-携带-转发”的机会性路由机制，这种消息复制的路由机制一般被划分为洪泛路由和副本限制路由2类. 典型的洪泛路由有直接传输(DT，direct transmission)、Epidemic[1]、Prophet[2]、FAD[3]等；副本限制路由有Spray and Wait[4-5]、Spray and Focus[6]和EBR[5]等；另外，基于节点社会行为的路由机制也是近年研究的热点[7].
消息复制的路由机制虽能有效提升数据传输的成功率、降低传输时延，但也直接导致了网络通信开销和存储开销大的不良后果，针对这种情况，笔者提出一种基于广播副本消除的数据传输策略(CRD，copy-removed data delivery scheme)，其基本思想利用广播信道辅助网络数据转发，及时清理节点消息队列，删除冗余信息，提高存储空间利用率. 仿真结果表明，CRD与现有的Epidemic、DT、Spray and Wait等路由机制相比有着更均衡的性能.
1 网络模型假定DTMSN初始部署时，多个传感器节点随机部署在一个N×N的正方形区域A内，基站处于中心. 节点在运动过程中将采集到的消息相互转发并最终送给基站(BS，base station). 基于实际应用，同时给出如下假设：
1) 网络支持2个通信频率. BS在频率f1上以恒定的大功率和固定周期T将已接收到的消息身份标识(ID，identification)广播出去，广播信号半径为C. 在广播信号范围内的节点能根据在频率f1上接收到的广播信息清理自身冗余消息副本，同时也可利用广播信号强度进行自身传输概率计算. BS和传感器节点利用频率f2进行通信，通信半径为R，其中C$\gg $R.
2) 所有节点的运动规律都遵循随机路点(RWP，random waypoint)随机运动模型. 实际中传感器节点往往并不知道每次运动的目的地，也不知道自身的速度和运动时间.
3) BS位置固定且能量无限. BS有2个同样的射频前端，分别工作在不同频率，以保证基站在频率f1上广播消息的同时也能在频率f2上进行通信.
4) 节点内有定时器，并可利用程序自由切换信道.
2 CRD数据传输机制 2.1 BS消息广播 2.1.1 消息生存时间计算消息生存时间(ST，survive time)，即消息在网络中存在的时间. 受节点消息队列空间的限制，消息不能永远保存在队列当中，因此需要将ST超过网络延迟容忍限度(DTV，delay tolerant value)的消息及时删除. 为了计算ST，首先假定每个消息的头部均包含该消息的ID及其ST. 当消息初次生成时，ST被赋值为0. 每个节点都有一个本地计时器，每当计时超时，ST就会增加1；当消息被转发时，由于消息交互的时间非常短，因此收发消息双方不改变该消息ST值.
2.1.2 BS消息广播与同步BS会实时统计所有已接收消息的ST值，将ST值小于DTV的消息ID以恒定的大功率在频率f1上进行周期性的广播，周期为T. 广播消息头部记录着广播ID和包含消息的数量. 当广播消息内有新的消息ID出现时，广播ID进行加1更新.
由于广播的周期为T，为了能让传感器节点切换到频率f1后，可及时地接收到广播消息而不至于过长等待，需要考虑基站与节点间的同步问题. 这里给出一个简单的网络松同步方法. 具体为：当某节点第一次切换到频率f1后，可打开一个较长的时间窗口接收广播消息. 一旦接收到广播消息，则节点将以此刻为起点，以T为周期设定自身定时器，下一次只在计时周期到达的时刻切换到频率f1，这样就可比较准确地接收到广播消息，不用等待时间过长.
2.2 数据传输节点传输概率表明节点与BS间通信的可能性，节点间消息转发依据节点传输概率进行. 网络模型中BS周期性以恒定的大功率在频率f1上进行消息广播，传感器节点将根据接收的广播信息清除自身的冗余消息副本，同时利用其信号强度判断自身的运动速度、相对于基站的距离和运动趋势，并根据这些信息计算自身的传输概率.
2.2.1 副本消除BS广播报文包含一个广播序号域，初始值为0，每个周期如果收到新的消息，则序号加1. 节点在接收到BS广播信息后，如果发现广播消息的广播序号与上一次接收的相同，则说明BS最近没有收到新的消息，也就没有副本可消除；相反，如果节点发现广播序号与上一次接收的不同，则根据报文内的消息ID在自身消息队列中进行查找，如果有相同ID的消息，则直接删除，以节省存储空间.
2.2.2 节点运动速度计算及运动趋势分析如图 1所示，假设节点以匀速v沿直线SD运动，节点以时间间隔τ定期接收BS的广播消息，假定节点在P1,P2,P3处接收到广播消息，根据信号传播衰减规律和信号强度可计算出各点与BS的距离l、节点运动速度v以及直线SD与BS的距离d，具体计算方法可参看文献[8]. d＞R时，表明节点运动过程中不会进入BS的通信范围，相反则可能进入. 综上，根据距离d以及信号强度的变化，节点即可判断自身相对于BS的运动趋势.
|
图 1 节点运动速度计算示意图 |
由于在RWP模型中，越靠近中心区域节点出现的概率密度越大，因此一般认为节点与BS的距离、相对于BS的运动趋势及方向对节点传输概率影响较大. 假设节点i与BS的距离为l，将节点i的状态进行划分并给出其传输概率Pi的计算方法. 具体方法如下.
连通态：Pi=1，l＜R，节点在BS通信半径内.
自由态：${{P}_{i}}=\frac{R}{2C}\frac{{{T}_{i}}}{{{T}_{i}}+\varepsilon }$，若l＞C，此时节点处于广播覆盖范围外，无法确定自身运动速度. 这时可认为节点在广播半径外的时间越长，其进入广播范围的可能性越大，概率也越大. 因此Ti表示节点i处于广播范围外的时间. 当节点重新进入广播覆盖范围后，Ti设为0，ε为正值常数.
背离态：${{P}_{i}}=\frac{R}{2l}\frac{R}{l}=\frac{{{R}^{2}}}{2{{l}^{2}}}$，若C＞l＞R，此时节点i朝远离BS方向运动，距基站越远，概率越低.
趋向态：${{P}_{i}}=\frac{R+l}{2l}$，若C＞l＞R且d＜R，此时节点i朝BS运动且有可能进入BS通信范围.
趋近态：${{P}_{i}}=\frac{R}{2l}\frac{R}{d}=\frac{{{R}^{2}}}{2ld}$，若C＞l＞R且d＞R，此时节点i趋近BS运动，但不可能进入BS通信范围.
选择态：若C＞l＞R且节点i速度为0，则节点处于选择态. 此时节点在下一次运动过程中根据运动方向的不同，有可能成为背离态、趋向态和趋近态中的一种，因此传输概率与运动的方向有关，具体为
| ${{P}_{i}}=\text{ }\left\{ \begin{align} & {{R}^{2}}/2{{l}^{2}}\sin \left( \frac{\pi }{2}-\alpha \right),0\le \alpha ＜\pi 2-\arcsin \frac{R}{l} \\ & R/2l+0.5,\frac{\pi }{2}-\arcsin \frac{R}{l}\le \alpha ＜\frac{\pi }{2}+\arcsin \frac{R}{l} \\ & {{R}^{2}}/2{{l}^{2}}\sin \left( \alpha -\frac{\pi }{2} \right),\frac{\pi }{2}+\arcsin \frac{R}{l}\le \alpha ＜\pi \\ & {{R}^{2}}\sin ~\left( \frac{3\pi }{2}-\alpha \right)/2{{l}^{2}},\pi \le \alpha ＜\frac{3}{2}\pi \\ & {{R}^{2}}\sin ~\alpha -\frac{3\pi }{2}2{{l}^{2}},\frac{3}{2}\pi \le \alpha ＜2\pi \\ \end{align} \right.$ |
其中α为选择移动的角度，为0≤α＜2π中的随机数.
2.2.4 数据传输节点间消息转发依传输概率进行. 节点在传输消息前首先通过握手信息了解其他各邻居节点的传输概率、消息队列剩余空间大小n以及已有的消息；根据这些信息，节点将传输概率大于自身的邻居节点按照传输概率由高到低进行排列，然后依次确定自身具有且对方没有的消息及其数量m，然后将这些消息分别进行传送. 向某一邻居节点传输消息的数量为min(m,n).
2.3 消息队列管理CRD中每个消息都包含一个转发域M，该域用于存放消息转发次数，随消息一同转发. 当消息刚生成时M=1，此后消息每转发一次，发送者都将该位进行一次乘2操作. M越大基本可表明该消息被转发的次数越多(M为消息副本数量的估值). CRD综合利用消息生存时间ST和M对消息队列进行管理.
2.3.1 消息丢弃方法消息的丢弃包括以下3种情况：
1) 当某个消息生存时间ST超过网络延迟容忍限度DTV的值时，消息要及时删除.
2) 当本地队列已满且节点自身有新消息生成时，则将ST值最大的消息删除，为自身新消息留出空间.
3) 如2.2.1所述，根据广播信息已知某一消息已经被BS接收，则将该消息删除.
2.3.2 消息传输优先顺序CRD在消息传输先后顺序的判定上综合利用ST和M值来完成. 节点首先根据M值对消息进行排序，优先转发M小的消息，在M相同的情况下，优先转发ST小的消息. 优先转发M值小的消息是为了确保网络中的消息都有均等的转发机会，而在此基础上优先转发ST小的消息则有利于降低消息的传输时延.
3 实验结果与分析笔者对CRD、二进制喷射等待机制(BS&W，binary spray and wait)、Epidemic和基于网络编码的有限缓存路由协议(NC-LB，network coding with limited buffer routing protocol)4种路由机制在Netlogo4.1.3平台下进行了仿真，并从消息传输成功率、节点平均传输消息数量和消息平均传输延时3个方面对各机制的性能进行了比较，同时对4种机制中的消息副本情况进行了分析. 仿真实验中，区域A为200 m×200 m的正方形区域，广播半径C为100 m. 假定节点采集消息的生成速率遵循平均到达时间为10 s的泊松过程，网络带宽为250 kbit/s，网络模拟运行时间为1 000 s. 其他网络参数如表 1所示. 需要指出的是，所有机制中消息的ST一旦大于DTV，则该消息被节点删除.
|
表 1 仿真实验参数 |
在默认参数条件下，4种传输策略的具体性能如表 2所示. 从表 2可以看出，NC-LB机制在传输成功率上具有一定的优势，消息平均延迟也相对较低，但由于该机制以Epidemic为基础，并在接收消息过程中基本不受消息队列大小限制，可通过编码方式与已有消息同时存储，因此通信开销极大，是传统Epidemic机制的数倍，若不加以限制则很难实用. Epidemic机制试图利用大量的消息复制来提升网络性能，但由于消息被盲目地转发，使得在传输成功率和消息传输延迟方面都不够理想，且通信开销也非常大. BS&W机制在spray阶段既能快速散播消息又限制了节点转发消息的数量，因此能以较低的通信开销获取不错的网络性能. CRD机制在平均传输时延方面相对于其他3种机制都有着明显的优势，同时在数据传输成功率和通信开销方面也比较优异，这主要是得益于及时的冗余副本删除、科学的转发概率计算和合理的队列管理机制，由于采用了选择性的消息转发机制，通信开销要远低于Epidemic机制，但较副本限制的BS&W机制稍高.
|
|
表 2 默认参数下仿真实验结果 |
在节点密度变化时，4种机制的仿真结果如图 2(a)～2(c)所示. 从图 2可以看出，随着节点密度的加大，节点间相遇机会的增多，4种机制的传输成功率都有所增加，其中CRD性能机制仅次于NC-LB. 另外，由于单位时间内到达基站的节点数量将增加，因此总体上消息的传输时延有所下降，其中CRD机制由于可选择转发的节点数量大大增加，因此传输时延下降得最为明显，也最低. 在通信开销上，由于Epidemic和CRD机制不限制消息副本的数量，因此通信开销也会明显提升.
|
图 2 节点密度变化时4种机制的仿真结果 |
当节点通信半径分别为3～7 m时，4种机制的仿真结果如图 3(a)～(c)所示. 通信半径的增加，使得节点间相遇及节点与基站相遇的频率大大提高，提升了消息传输成功率，降低了传输时延. 由于Epidemic机制没有对副本进行限制，直接导致了节点消息队列很快被填充满，导致传输时延改善不明显，且通信开销急剧增加. CRD机制采用选择转发的机制，一定程度上限制副本数量，好处是传输延时快速下降，但通信开销也迅速增加，而BS&W由于受到副本限制，通信开销基本没有改变，NC-LB通信开销仍然最大.
|
图 3 通信半径变化时4种机制的仿真结果 |
节点速度变化时的仿真结果如图 4(a)～(c)所示. vmax越大，节点速度越高，单位时间内遇到的节点数量就会提升，与基站发生连接的可能性也会增加. 因此4种机制的数据传输成功率都不同程度的有所升高，消息传输延迟也总体趋向下降，CRD延迟最小. 虽然节点速度增加了，但是由于受到副本数量限制，BS&W机制的通信开销基本上没有变化，而Epidemic机制和CRD机制在通信开销上有着相对明显的增加，NC-LB机制通信开销最大.
|
图 4 节点速度变化时4种机制的仿真结果 |
队列长度越长表明节点能存储的消息越多. 如图 5(a)所示，随着队列长度的加大，节点能容纳更多的消息及副本，帮助消息有更大几率以低延迟传输到基站，因此投递率和延迟性能都有提升. 但消息队列长度的加大导致了Epidemic、CRD网络通信开销也随之增大；但BS&W与NC-LB机制增加相对平缓. NC-LB机制无论队列长短，消息都会在编码后再存储，因此队列长度对通信开销的影响并不大.
|
图 5 消息队列变化时4种机制的仿真结果 |
以往在众多的文献当中通常将消息副本数量作为衡量延迟容忍网络(DTN，delay tolerant network)网络通信开销的一项指标. 虽然平均消息副本数量越多，网络的通信开销一般也越大，但通过参考图 2(c)～5(c)以及各种机制在不同消息队列长度下的平均副本数量，如图 6所示，可以看到，平均消息副本的多少与网络通信开销并没有绝对的必然联系. CRD机制之所以能利用有限的通信开销产生最多的消息副本，主要原因在于合理的队列管理机制使得有限的消息队列空间利用更加充分，消息在队列中的分布更加合理，消息在网络中分布得更为均衡. 但在消息队列空间比较充裕的情况下，CRD与Epidemic机制的平均副本数量和消息总量是基本相同的.
|
图 6 消息队列长度变化情况下的消息副本数量 |
提出的基于双频通信和副本消除的数据传输策略，在基本不增加硬件开销的基础上，使用广播频率和通信频率2个频段完成节点运动状态的判断和冗余消息消除，能较好地达到通信开销、传输时延和数据传输成功率的有效平衡.
| [1] | Vahdat A, Becker D. Epidemic routing for partially connected Ad hoc networks[R]. Technical Report, CS-200006.Durham: Duke University, 2000. |
| [2] | Lindgren A, Doria A, Schelén O. Probabilistic routing in intermittently connected networks[J]. SIGMOBILE Mobile Computing Communications Review , 2003, 7 (3) :19–20. doi:10.1145/961268 |
| [3] | Wang Yu, Wu Hongyi, Dang Ha, et al. Analytic, simulation, and empirical evaluation of delay/fault-tolerant mobile sensor networks[J]. IEEE Trans on Wireless Communications , 2007, 1 (11) :3287–3296. |
| [4] | Spyropoulos T, Psounis K, Raghavendra C S. Efficient routing in intermittently connected mobile networks: the single-copy case[J]. IEEE/ACM Trans on Network , 2008, 16 (1) :63–76. doi:10.1109/TNET.2007.897962 |
| [5] | Samuel C N, Mehedi B, Robin K. Encounter-based routing in DTNs[C]//INFOCOM'09, 2009: 846-854. |
| [6] | Spyropoulos T, Psounis K, Raghavendra C S. Efficient routing in intermittently connected mobile networks: the multiple-copy case[J]. IEEE/ACM Trans on Network , 2008, 16 (1) :77–90. doi:10.1109/TNET.2007.897964 |
| [7] | Abdelkader T, Naik K, Nayak A. A performance comparison of delay-tolerant network routing protocols[J]. IEEE Network , 2016, 30 (2) :46–53. doi:10.1109/MNET.2016.7437024 |
| [8] | 杨奎武, 郑康锋, 杨义先, 等. 基于运动状态的延迟容忍移动传感器网络数据传输策略[J]. 通信学报 , 2010, 31 (11) :138–146. Yang Kuiwu, Zhen Kangfeng, Yang Yixian, et al. A motion state-based data delivery scheme of delay tolerant mobile sensor networks[J]. Journal on Communications , 2010, 31 (11) :138–146. |