2. 四川师范大学 基础教学学院, 成都 610068
提出了一种基于sink简单固定轨迹的动态数据传输算法, 算法由数据传输策略和队列管理机制组成, 适用于异构延迟容忍移动无线传感器网络.在每一次运动开始, 首先判断节点是否可以直接传输消息给汇聚点, 然后根据节点能量消耗和传输延迟计算出不同时刻各节点的传输概率, 节点根据传输概率进行消息传输或转发.队列管理则根据不同类型消息的生存时间和传输次数来决定对消息的转发和丢弃(被动或主动).实验结果验证了算法的有效性.
2. College of Fundamental Education, Sichuan Normal University, Chengdu 610068, China
A dynamic data delivery algorithm is proposed which is composed by data transmission strategy and queue management mechanism. It can be applied to heterogeneous delay tolerant mobile sensor networks. Firstly judge each node whether it can transmit messages directly to the sink; then calculate the node's forward probability at different time. Thereafter the forward probability is calculated based on energy consumption and transmission delay. Each node forwards message by the right method. Queue management obey different survival time and transmission counts of different nodes. Simulations show that this data algorithm has a better effectiveness.
如何提高网络的数据传输成功率和均衡网络能量消耗，是目前异构容忍延迟移动无线传感器网络[1-2](HDTMSN, heterogeneous delay tolerant mobile sensor networks)中研究和应用的热点.引入移动sink已经成为有效提高网络性能的主要手段之一，但现存算法主要有以下不足：不合理的数据传输方案增大了网络时延[3]，能耗严重，网络传输延迟较高、可扩展性差.笔者提出了一种高效的基于sink简单移动轨迹的动态数据传输算法(DTPF, dynamic data transmission algorithm based on path-fixed sink)，包括数据传输和队列管理2部分，实验结果与DT[4]、Flooding[5]和SRAD[6]比较，验证了其网络寿命相对较长，有更小的传输延迟和更高的数据传输成功率.
1 模型与问题描述设N个不同类型的异构节点(箭头代表运动方向)随机布署在半径为R的圆形监测区域内，石高涛等[7]提出一种具有负载平衡的移动协助数据收集模式，并论证了当缓冲区位于距圆心处
|
图 1 数据传输模型图 |
1) 节点i首先判断自己此刻能否直接和汇聚点发生通信.
2) 节点i判断自己是否与缓冲区有相交趋势.连接节点i当前位置I(x1，y1)和目的点D(x2，y2)：
① 若I在Z1区域，即
|
图 2 节点与缓冲区内相交 |
② 若I在Z2区域，即
|
图 3 节点与缓冲区外相交 |
③ 如果I和D都在Z1区域，且圆心到线段ID的距离小于L，则线段ID与sink轨迹相交，如图 4所示.
|
图 4 节点与缓冲区直线相交 |
3) 若1)、2) 均不满足，则计算ID与sink移动轨迹的最短距离di_min.如果di_min < dsink，节点i可以根据2.2节的转发概率进行消息的直接传输；否则，需要选择下一跳进行转播.
2.2 消息传输(转发)概率节点i直接发送消息lj至汇聚点的能量消耗为
|
(1) |
其中：Eelec表示无线电路接收或者发送每比特数据的能量消耗，εmpdi_min2和εmpdi_min4表示发送每比特数据时放大器所消耗的能量，do为通信阈值当发送方与接收方之间的通信距离di_min小于do时适用于自由空间模型，发送方发送数据的能量损耗与距离的平方成正比；否则，适用于多径衰落信道模型，发送方发送数据的能量损耗与通信距离的4次方成正比.
设节点i此时有M′个邻居节点，Ecur_i为i的目前剩余能量.通过握手i获得邻居节点的消息传输距离、运动速度、通信半径等信息，优先选取与汇聚点运动轨迹有交点的邻居节点.假若可供选择的任意节点u的目前剩余能量为Ecur_u，消息传输距离为du_min，与节点i之间的相隔距离为di_u；任意节点w的当前剩余能量为Ecur_w，消息传输距离为dw_min，与节点i之间的距离为di_w，则计算并判断
将di_u代替式(1) 中的di_min，计算出ETx_iu(lj, di_u).节点u接收消息lj所需的能量消耗为
|
(2) |
同理得，消息lj从节点u发至sink的能耗ETx_uO(lj, du_min).消息lj通过节点u转发至sink的能耗为
|
(3) |
定义1(能耗因子) 能耗因子ω(E)是节点i传输消息到sink的能量消耗和当前剩余能量Ecur_i之间的比值，且0≤ω(E)≤1.
节点i直接发送消息lj到sink的能耗因子为
|
(4) |
如果节点i的消息lj要通过节点v转发到sink，则能量消耗由消息lj从节点i转发至节点v的能量消耗、节点v接收消息lj的能量消耗、节点v发送消息lj到sink的能量消耗3部分组成.因此，消耗因子为
|
(5) |
定义2(延迟因子) 延迟因子ω(D)表明了消息lj发至sink的时间与lj的延迟容忍度的关系，且0≤ω(D)≤1.
如果节点i直接发送消息lj到sink，延迟因子为
|
(6) |
其中：ti为节点i直接发送消息lj到汇聚点所需的最短时间，Tj为当前等待发送的消息lj的延迟容忍度.
如果节点i通过节点u转发消息lj，延迟因子为
|
(7) |
其中：tu为节点i通过节点u转发消息lj到汇聚点所需的最短时间.
定义3(传输概率) 传输概率Pi表明节点i直接发送消息至sink的可能性，0≤Pi≤1. Pi的表达式为
|
(8) |
其中α、β为非负权重系数，且满足α+β=1.
定义4(转发概率) 转发概率Fi_u意味着节点i通过节点u转发消息lj到sink的可能性. Fi_u的表达式为
|
(9) |
队列管理机制综合考虑了不同传感器节点产生的消息具有不同的延迟容忍度、存活时间和成功传输次数因素.每个数据消息的头部都包含一个域，记录消息的存活时间和成功传输次数.当消息初次产生时，存活时间始初化为0，其数值随着计时逐步增大，消息产生得越早，存活时间就越长；成功传输次数始值为0，消息每被成功地转发一次，成功传输次数就加1.
1) 被动丢弃
首先，若消息的存活时间大于整个网络的延迟容忍限度值θ或者此类消息的延迟容忍限度值ε，说明该消息已经无效，可以立刻被丢弃.
其次，若消息的成功传输次数大于网络阈值Φ或者此类消息传输上限η，则代表此消息已确保被发送到汇聚点，可以立刻被丢弃.
如果队列存储已满或剩余存储空间不够，分别比较新消息和队尾消息的存活时间、成功传输次数和延迟容忍度，淘汰掉存活时间、成功传输次数和延迟容忍度相对较小的消息.
2) 主动丢弃
汇聚点会记录最近一段时间已接收到的消息编号，定期向全网广播，节点检查自己的缓存队列，删除所有已被接收的消息或消息副本.
3) 消息队列实现
存储队列内的数据消息首先按照各自的存活时间由短到长插入队列，如果出现多个消息有相同的存活时间，则按照成功传输次数再由小到大插入排序；如果出现2个或者2个以上的消息有相同的存活时间和成功传输次数，则按照延迟容忍度升序排列.存活时间越短、成功传输次数越小且延迟容忍度越小的消息越容易被排在队首并拥有优先发送权.
4 实验分析定义100个传感器节点随机分布在半径R=113 m的圆形区域，符合RWP模型.设网络带宽为10 kbit/s，传输半径为2~4 m，运动速率为1~5 m/s，消息队列长度为20~60 kbit，节点初始能量为5~15 J.
4.1 4种算法的性能对比分析4种算法的性能可知，DT算法中消息副本数为1，但交付周期过长且缺少队列管理机制；Flooding算法中产生了大量的消息副本；SRAD算法虽然在选择下一跳时尽可能考虑与汇聚点进行通信的节点，但并没有综合考虑节点与汇聚点通信的可能性和能量消耗对传输概率的影响，设计队列管理机制时也未考虑网络的异构特性；DTPF算法引入了移动sink，尽量选择以较低的能量消耗和较小的传输延迟的下一跳进行转发，采取了有效的队列管理机制，因此综合性能更优.
4.2 运动速度和存储队列长度的影响由图 5可以看出，4种算法的传输成功率都随着运动速度的增大而逐渐上升，DTPF算法则有着最高的传输成功率.这是因为节点与节点(包括汇聚点)之间相遇的概率随着运动速度的增大而增大.
|
图 5 运动速度改变对传输成功率的影响 |
存储队列的长度越长，能容纳的消息就越多，消息被存放的时间就越久，消息越有可能被发送至汇聚点.如图 6所示，除了DT算法的消息副本数保持不变，其他算法的平均消息副本数目随着存储队列长度的增长而不断增大.
|
图 6 队列长度改变对消息副本数的影响 |
与已有研究对比，DTPF有以下3方面优点.
1) DTPF设定了一种简单sink移动轨迹，利用移动sink进行数据收集，有效减少了消息转发次数.
2) 提出了合理的消息传输机制，节点的传输概率和转发概率都需要结合能耗因子和延迟因子进行计算，降低了传输(转发)消息的能量消耗和传输延迟.
3) 设计了一种适用于异构网络的队列管理策略，有效地控制了HDTMSN的消息副本冗余，节省了网络传输能耗和网络带宽.
今后将对移动sink轨迹和数据传输策略做进一步的改进，使其能运用于实际的网络环境中.
| [1] |
刘唐, 彭舰, 杨进. 异构延迟容忍移动传感器网络中基于转发概率的数据传输[J]. 软件学报, 2013, 24(2): 215–229.
Liu Tang, Peng Jian, Yang Jin. Data delivery for heterogeneous delay tolerant mobile sensor networks based on forwarding probability[J].Journal of Software, 2013, 24(2): 215–229. |
| [2] |
杨奎武, 郭渊博, 郑康锋, 等. 延迟容忍移动传感器网络高效广播数据传输机制[J]. 北京邮电大学学报, 2013, 36(1): 1007–5321.
Yang Kuiwu, Guo Yuanbo, Zheng Kangfeng, et al. An efficient broadcast transmission scheme for delay tolerant mobile sensor networks[J].Journal of Beijing University of Posts and Telecommunicatons, 2013, 36(1): 1007–5321. |
| [3] | Guerroumi M, Badache N, Moussaoui S. Sink mobile for efficient data dissemination in wireless sensor networks[J].Networked Digital Technologies, 2012, 293(8): 635–645. |
| [4] | Wang Yu, Wu Hongyi. Delay/fault-tolerant mobile sensor network (DFT-MSN): a new paradigm for pervasive information gathering[J].Mobile Computing, IEEE Transactions on, 2007, 6(9): 1021–1034. doi: 10.1109/TMC.2007.1006 |
| [5] | Vahdat A, Becker D. Epidemic routing for partially connected Ad hoc networks[R]. Technical Report CS-200006, Duke University, 2000. |
| [6] |
朱金奇, 刘明, 龚海刚, 等. 延迟容忍移动传感器网络中基于选择复制的数据传输[J]. 软件学报, 2009, 20(8): 2227–2240.
Zhu Jinqi, Liu Ming, Gong Haigang, et al. Selective replication-based data delivery for delay tolerant mobile sensor networks[J].Journal of Software, 2009, 20(8): 2227–2240. |
| [7] |
石高涛, 廖明宏. 传感器网络中具有负载平衡的移动协助数据收集模式[J]. 软件学报, 2007, 18(9): 2235–2244.
Shi Gaotao, Liao Minghong. Movement-assisted data gathering scheme with load-balancing for sensor networks[J].Journal of Software, 2007, 18(9): 2235–2244. |