暂态社区感知的ICWN数据转发机制

2017-12-04杜剑夏元轶赵俊峰王峥王鹤

电信科学 2017年11期

关键词：投递中继无线网络

杜剑, 夏元轶, 赵俊峰, 王峥, 王鹤

（1. 北京智芯微电子科技有限公司，北京 100192；2. 国网江苏省电力公司信息通信分公司，江苏南京 210024）

暂态社区感知的ICWN数据转发机制

杜剑1, 夏元轶2, 赵俊峰2, 王峥1, 王鹤1

（1. 北京智芯微电子科技有限公司，北京 100192；2. 国网江苏省电力公司信息通信分公司，江苏南京 210024）

为了有效解决间断连接无线网络中的数据转发问题，提出了一种暂态社区感知的数据转发机制，运用半马尔可夫链模型描述节点在多个地理位置间的转移过程，预测节点在未来相遇的时间概率分布，确定节点相遇位置和时间，为下一跳中继节点的选择提供了理论依据。实验数值表明，与传统算法相比，所提机制能有效提高节点相遇预测的准确性，在数据成功投递率和传输时延等性能上都有较大的提升。

间断连接无线网络；数据转发；暂态社区；相遇预测；半马尔可夫模型

1 引言

间断连接无线网络（intermittentl connected wireless network，ICWN）是指不需要源节点和目的节点在转发数据前建立完整的端到端路径，利用节点移动带来的相遇机会，以更加灵活的“存储—携带—转发”的协作方式逐跳进行传输[1]。该网络具有自组织、节点稀疏、间歇连接、资源受限、拓扑动态变化等特性[2]。在这种复杂多变的组网环境下，设计能够满足间断连接无线网络通信需求的数据转发机制成为研究间断连接无线网络的关键问题[3]。

在间断连接无线网络中，源节点和目标节点之间并不依靠始终连通的完整链路进行数据的传输[4]，且源节点与中继节点之间的连接也随着时间的变化而不断变化，任意成对节点间的通信链路都随时会遭遇断裂[5]，这种间断性的端到端连接和不断变化的网络拓扑使得传统移动自组织网络的数据转发机制难以直接应用到间断连接无线网络中[6]。

目前，国内外研究人员已经提出了一些应用于间断连接无线网络的数据转发机制。Becker等人[7]提出了传染路由（epidemic routing）机制，其核心思想是源节点将数据复制、转发给任何与其相遇的节点，一定程度上提高了数据的传输效率，但洪泛型的数据转发机制需要占用大量的缓存空间，消耗大量能量，而节点自身资源很有限，导致该机制分组丢失率较高。社会学的主要研究内容是人类在时间、空间内的交互作用，基于社会理论，Hui等人[8]提出了一种名为多标签的数据转发机制，将网络划分为若干社区，节点在转发数据时选择通信范围内与自己同社区的节点作为下一跳节点，但当源节点与目的节点所属社区距离较远时，数据成功投递率不高。为此，参考文献[9]中提出Bubble-Rap算法，在选择中继节点时考虑节点及节点所在社区的活跃度，根据不同需求选择下一跳节点。针对间断连接无线网络的分裂性特点及节点移动行为的趋同性，参考文献[10]提出SimBet机制，在选择中继节点时综合考虑节点向心度和相似度，节点向心度描述两节点之间的依赖程度，相似度表征节点移动行为的趋同性，根据节点向心度和相似度评估数据转发效用值，以此选择下一跳节点。上述机制中，节点转发数据时仅选择未来与目的节点相遇概率高或效用值大的节点作为下一跳节点，其主要关注的是未来两个节点能否相遇，而没有考虑节点相遇的时间和地理位置。而实际情况中，节点不会无休止地缓存数据，且数据自身存在时效性，因此设计数据转发机制时既要保证数据的有效传递，也要考虑数据的时效性。

针对上述问题，本文提出了一种暂态社区感知的数据转发机制（transient community awared data forwarding mechanism，TCDFM），运用半马尔可夫模型，准确预测节点未来相遇的时间和地理位置，更加合理地选择下一跳中继节点，在保障数据成功投递率的同时，降低数据传输时延，保证数据的时效性。

2 网络环境

间断连接无线网络中节点的社会属性使节点的移动具有一定规律性[11]，但移动轨迹并不固定，网络中节点以一定次序在几个地理位置之间进行访问，节点在到达目标位置后，以一定的概率选择在该位置滞留一定时间或者直接离开。本文假设在校园场景下，地理位置分别为教室、食堂、图书馆等建筑，节点为持有短距离无线通信设备的学生和老师。节点各自遵循自己的日程表进行移动。其中，社会属性作为节点的内在属性，则会在很大程度上影响节点的移动模式，呈现出某时段在有限移动范围内高度活跃，在另一时段移动相对迟缓，将这种特性定义为节点的暂态特性。通过进一步研究发现，节点的暂态特性主要表现在时间和地理位置两个方面，节点往往趋向于在特定时间区间的某一地理位置聚集。那么在ICWN中，若干节点在某个时间区间内常驻在某个明确的地理范围内，且在此范围内的节点保持紧密的联系，从而可以将这些节点进行聚合形成稳定连通的 ICWN子网，将其称为暂态社区（temporal community，TC）。

为了构建暂态社区，节点为数据设定一个TTL值，TTL值到期，节点自动将数据删除。具体数据转发过程如下：当一个节点需要转发数据时，首先筛选邻居节点中未来能与目标节点相遇的节点作为候选中继节点；然后，节点执行本文预测算法，预测各候选中继节点与目标节点的相遇时间，并与数据的TTL值比对，淘汰在TTL到期前无法与目标节点相遇的候选中继节点；最后，计算候选中继节点中与目标节点的相遇概率，选取相遇概率最大的节点作为下一跳节点，如果候选中继节点与目标节点相遇的概率值均小于当前节点，则数据继续缓存在本地节点。图 1为校园场景下本文数据转发机制示意，节点 A需要转发数据给节点 E，当前时刻节点A与室友节点B和节点C同处于宿舍内。基于节点历史移动信息，节点 A预测到在TTL到期之前，相比于节点C，节点B更有可能与节点E相遇，所以节点A将数据转发给节点B。节点B不久后与节点E相遇，进而将数据转发给节点E。

图1 校园场景下本文数据转发机制示意

3 节点行为预测

3.1 节点历史行为信息交互

为了准确预测节点的移动行为，网络中的每个节点都需要尽可能地了解其他节点的历史移动信息。本文将节点的移动信息设计为一个5元组其中，P是节点在不同地理位置之间的转移概率矩阵，SP是节点在各个位置的滞留时间概率分布，T是节点地理位置变化的起始时间，ID和LocID分别是节点 ID和节点所在位置的ID。当两个节点相遇时，节点间会交换历史移动信息。节点接收到其他节点的历史移动信息后，通过5元组内的T值判断数据的新旧，然后将较新的数据在本地缓存。

若节点S想要转发数据给节点D，则首先查询本地数据中节点 D 的历史移动信息则节点 D在时间t时所处的位置由式（1）得到：

其中，Wt代表节点D在时间t的地理位置，L是地理位置集合。

3.2 行为参数评估

预测两个节点的相遇时间和地理位置需要获知两个参数：地理位置转移概率矩阵和滞留时间概率分布，两个参数均由节点历史移动信息获知。

图2 地理位置转移示意

节点n当前位于地理位置i，随后转移到地理位置j，节点在位置i的滞留时间概率分布函数可以定义为：

当网络达到稳定状态时，移动历史信息为滞留时间分布的计算提供依据。按照式(4)的方式计算＜k)：

3.3 节点状态转移概率评估

为了提高间断连接无线网络中暂态社区时空特征对节点移动行为预测的有效性，本文使用时间齐次的半马尔可夫链模型模拟节点n的移动过程，该过程可以表示为()。节点所处的不同状态用地理位置 ID表示，记作 L=1,2,3,…,l。一个节点在两个地理位置之间的移动对应节点在马尔可夫链中两个状态之间的转移。假设不同状态间的转移概率具有马尔可夫链的无记忆性，即节点n从状态转移到状态的概率是独立于状态的，这个转移行为仅与节点当前状态相关。基于上述特点，随机过程(符合标准的时间离散马尔可夫链的特性。随机变量表示节点n由状态向转移的时间，随机变量（）描述了节点n在地理位置i的滞留时间。本文节点在某个地理位置的滞留时间并不包含节点在两个状态之间转移所需要耗费的时间。

4 转发决策

间断连接无线网络虽然是延迟可容忍网络，但是数据具有时效性，超过时效的数据即使转发到目标节点也没有意义，而且在网络中持续转发、缓存时，数据也是对网络资源的浪费。本文认为数据的最大可接受时延就是数据的生存时间TTL。令节点n表示源节点的邻居节点，N是当前节点的所有邻居节点的集合，d表示目标节点，选取与目标节点相遇概率最大的节点作为下一跳节点：

利用上述方法，选择具有最高效用值的节点作为中继节点转发数据，即在未来的TTTL单位时间内与目标节点相遇概率最高的节点。如果所选的中继节点未来与目标节点相遇的概率小于当前节点，则数据继续缓存在当前节点，直至更优的中继节点出现，或者待TTL值到期后将数据删除。

5 仿真结果分析

本文采用间断连接无线网络环境 ONE[12]仿真平台进行数据转发策略性能验证，并与典型的数据转发机制Prophet及Bubble-Rap进行对比，以验证所提出机制TCDFM的性能。仿真参数见表1。

表1 仿真参数设置

5.1 节点数量对数据转发策略的影响

间断连接无线网络是典型的节点分布稀疏网络，网络中节点的数量直接影响节点相遇机会，最终影响数据转发机制整体性能。因此，首先分析节点数量对不同数据转发机制的影响，结果如图1所示。

图3 节点数量对数据成功投递率的影响

图4 节点数量对平均传输时延的影响

由图3、图4可以看出，随着网络中节点数量的增加，TCDFM和Bubble-Rap机制在数据成功投递率上呈现平稳上升趋势，相比前两者，Prophet则呈现反向趋势。TCDFM与两种算法的数据传输时延均随着节点数量的增加呈现下降趋势。本文算法在数据成功投递率和平均传输时延所呈现出的性能均是最优的，数据成功投递率分别比Bubble-Rap算法和Prophet算法平均高出13.2%和17.9%，平均传输时延分别比 Bubble-Rap和Prophet平均低26.8%和37.3%。主要原因为随着网络中节点数量的增多，节点间相遇机会增加，为中继节点的选择提供了更多的选择，明确了中继节点进行数据投递的目标，进而提高了数据成功投递率。在Prophet算法中，随着数据副本在网络中大量分发，网络资源被大量占用，导致基于相遇概率的多副本分发的 Prophet算法会进行大量的数据复制、转发，抑制了副本的有效传递，降低了网络性能，最终造成了数据传输时延较大。TCDFM 算法考虑了中继节点能否在数据时效性内将数据转发给目标节点，在中继机会增多的同时，能够挑选更优的中继节点进行数据转发，如果数据在有效时间内不能成功投递，则立即删除，避免资源浪费对其他数据的投递产生影响，从而降低了数据的传输时延。

5.2 数据TTL值对数据转发策略的影响

TTL表示网络中数据的生存时长，不同的TTL值在一定程度上影响了网络中待转发数据的数量。因此，TTL值对数据转发策略的性能和网络的存续时间影响很大。图5、图6分别表示在不同TTL值下，不同算法的数据的成功投递率和平均传输时延。

图5 TTL值对数据成功投递率的影响

由图5、图6中可以看出，随着TTL值增加，3种路由算法的数据成功投递率均先上升后下降，同时，随着TTL值的增加，数据传输的平均时延

图6 TTL值对平均传输时延的影响

随之增加。本文 TCDFM 算法在数据成功投递率上分别比Prophet算法和Bubble-Rap算法平均高出 12.3%、17.2%，而数据的平均传输时延则比Prophet算法和 Bubble-Rap算法分别低 19.6%、14.1%。主要原因为数据的 TTL值较小时，节点间还未产生相遇机会，数据就有可能被删除，数据的成功投递率会比较低。而当TTL值较大时，网络中的数据会始终保存在节点的缓存空间中，即使数据成功投递到目标节点，网络中仍然包含大量数据副本，极大地浪费网络资源，影响网络的性能。因此，在TTL值增大的过程中，数据的成功投递率会随之增高，在达到峰值后，继续增大TTL值就会造成网络拥塞，数据的正常传输受阻，数据成功投递率开始下滑，同时，平均传输时延增大。

6 结束语

为了实现间断连接无线网络中数据的高效可靠传输，本文提出了一种暂态社区感知的数据转发机制，利用时间齐次的半马尔可夫链模型进行节点相遇预测，确定两个节点未来在指定时间指定位置的相遇概率。节点需要转发数据时，从邻居节点中筛选在TTL值到期之前与目标节点相遇的节点作为候选中继节点，选择各候选中继节点中与目标节点相遇概率最大的节点作为下一跳中继节点。仿真结果表明，与传统路由机制相比，所提出的机制能够在保证较高数据投递率的同时，降低数据的传输时延，有效地提高网络可靠性。

[1] WU D P, ZHANG H P, WANG H G, et al. Quality of protection(QoP)-driven data forwarding for intermittently connected wireless networks[J]. IEEE Wireless Communication, 2015,22(4): 66-73.

[2] WU D P, HE J, WANG H G, et al. A hierarchical packet forwarding mechanism for energy harvesting wireless sensor networks[J]. IEEE Communication Magazine, 2015, 53(8): 92-98.

[3] WU D P, WANG Y Y, WANG H G, et al. Dynamic coding control in social intermittent connectivity wireless networks[J].IEEE Transactions on Vehicular Technology, 2016, 65(9):7634-7646.

[4] WANG R Y, YANG H P, WANG H G, et al. Social overlapping community aware neighbor discovery for D2D communications[J]. IEEE Wireless Communications, 2016, 23(4): 28-34.

[5] FENG M, MAO S, JIANG T. Joint duplex mode selection,channel allocation, and power control for full-duplex cognitive femtocell networks[J]. Digital Communications and Networks,2015, 1(1): 30-44.

[6] WU D P, ZHANG P N, WANG H G, et al. Node service ability aware packet forwarding mechanism in intermittently connected wireless networks[J]. IEEE Transaction on Wireless Communications, 2016, 15(12): 8169-8181.

[7] BISTA B B. Improving energy consumption of epidemic routing in delay tolerant networks[C]//International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, July 6-8, 2016, Fukuoka, Japan. New Jersey: IEEE Press, 2016: 278-283

[8] SONG L, LI Y, FAN S, et al. Social-based multi-label routing in delay tolerant networks[C]//IEEE Fourth International Conference on Big Data and Cloud Computing, Dec 3-5, 2014, Sydney, Australia. New Jersey: IEEE Press, 2014: 402-407.

[9] GUPTA A, AGRAWAL A, NAGRATH P. Variant of BUBBLE rap forwarding algorithm for delay tolerant networks[C]//International Conference on Computational Techniques in Information and Communication Technologies, March 11-13, 2016, New Delhi, India. New Jersey: IEEE Press, 2016:63-68.

[10] SHRESTHA N, SASSATELLI L. Inter-session network coding-based policies for delay tolerant mobile social networks[J].IEEE Transactions on Wireless Communications, 2016, 15(11):7329-7342.

[11] 潘剑飞, 徐丽丽, 董一鸿. 动态社区演化研究进展[J]. 电信科学, 2017, 33(1): 24-33.PAN J F, XU L L, DONG Y H. Research progress of dynamic community evolution[J]. Telecommunications Science, 2017,33(1): 24-33.

[12] ODA T, ELMAZI D, SPAHO E, et al. A simulation system based on ONE and SUMO simulators: performance evaluation of direct delivery, epidemic and energy aware epidemic DTN protocols[C]//International Conference on Network-Based Information Systems, Sept 2-4, 2015, Taipei, China. New Jersey:IEEE Press, 2015: 418-423.

Transient community awared data forwarding mechanism for intermittent connected wireless network

DU Jian1, XIA Yuanyi2, ZHAO Junfeng2, WANG Zheng1, WANG He1
1. Beijing Smartchip Microelectronics Technology Co., Ltd., Beijing 100192, China 2. Information & Telecommunication Branch of State Grid Jiangsu Electric Porer Company, Nanjing 210024, China

In order to solve the problem of data forwarding in intermittent connected wireless network effectively, a transient community awared data forwarding mechanism for intermittent connected wireless network(ICWN) was proposed. Utilizing the semi-Markov chain model, the transfer process of nodes’s between multiple geographic locations was described and the time probability distribution of nodes’ encountering in the future was predicted, then the encountering time and locations could be obtained, which provided theoretical basis for the selection of next relay node. Experiment results show that the proposed mechanism can effectively improve the forecasting accuracy of nodes’ encounter and has a great improvement in the data delivery ratio and transmission delay.

intermittent connected wireless network, data forwarding, transient community, encounter forcasting,semi-Markov model

Science and Technology Project of State Grid (No.526800150007)

TP393

10.11959/j.issn.1000−0801.2017262

2017−07−20；

2017−08−31

国家电网公司科技基金资助项目（No.526800150007）

杜剑（1987−），男，北京智芯微电子科技有限公司中级工程师，主要研究方向为集成电路与传感芯片在电力中的应用。