具有传输成功率保证的概率路由算法的TTL预测模型

doi:10.3969/j.issn.0372-2112.2018.11.015

电子学报 ›› 2018, Vol. 46 ›› Issue (11): 2679-2687.DOI: 10.3969/j.issn.0372-2112.2018.11.015

具有传输成功率保证的概率路由算法的TTL预测模型

马学彬, 王应彪, 高瑞超, 张晓娟

内蒙古大学计算机学院, 内蒙古自治区呼和浩特 010021

收稿日期:2017-11-07 修回日期:2018-04-11 出版日期:2018-11-25
- 作者简介:
- 马学彬 男,1981年4月出生,内蒙古大学副教授,研究方向为无线网络、移动IP、延迟容忍网络、信息安全.E-mail:csmaxuebin@imu.edu.cn;王应彪 男,1989年12月出生,内蒙古大学硕士研究生,研究方向为计算机网络.
- 基金资助:
- 国家自然科学基金 (No.61162006）; 国家自然科学基金应急管理项目 (No.61751214）; 内蒙古自然科学基金 (No.2018MS06026）

The TTL Prediction Model of Probability Routing Algorithm with the Transmission Rate Guaranteed

MA Xue-bin, WANG Ying-biao, GAO Rui-chao, ZHANG Xiao-juan

School of Computer, Inner Mongolia University, Hohhot, Inner Mongolia 010021, China

Received:2017-11-07 Revised:2018-04-11 Online:2018-11-25 Published:2018-11-25

摘要/Abstract

摘要： 概率路由算法是机会网络中一种常用的路由算法，其TTL的设置将直接影响路由的性能.本文首先利用马尔可夫链对概率路由的转发过程进行建模，并从消息的传输成功率和传输延时方面进行性能评估，不仅可以计算出一个消息从源节点到目的节点所需的传输延时，还可以预测出在给定传输成功率下所需要的最短消息生存周期TTL，这对于TTL的设置具有理论上的指导作用.其次，本文建立的预测模型还可以使一些无法到达目的节点的消息及时被删除，从而减少不必要的转发，达到节约网络资源的目的.最后，在两个真实数据集中的实验结果表明，本文提出的模型能够为概率路由中TTL值的准确设置提供有效参考.

关键词: 机会网络, 概率路由算法, 预测模型, 传输成功率, 传输延时

Abstract: Probabilistic routing algorithm is a common routing algorithm in opportunistic networks, and its TTL will directly affect the routing performance. Firstly, in the paper we uses Markov chain model to evaluate the transmission rate and the transmission delay of probabilistic routing. It can not only calculate the transmission delay for a message from a source node to a destination node, but also can predict the shortest TTL in a given transmission rate, which can provide theoretical guidance for the setting of TTL. Secondly, this prediction model can delete the messages which cannot be relayed to destination nodes to reduce unnecessary forwarding. Therefore, The model can be used to save the network resources maximally. Finally, we experimentally evaluate our model on two real data set, and demonstrate that it can provide a powerful reference for the setting of TTL values accurately in probabilistic routing.

Key words: opportunistic networks, probability routing algorithm, prediction model, transmission rate, transmission delay

中图分类号:

TN92

马学彬, 王应彪, 高瑞超, 张晓娟. 具有传输成功率保证的概率路由算法的TTL预测模型[J]. 电子学报, 2018, 46(11): 2679-2687.

MA Xue-bin, WANG Ying-biao, GAO Rui-chao, ZHANG Xiao-juan. The TTL Prediction Model of Probability Routing Algorithm with the Transmission Rate Guaranteed[J]. Acta Electronica Sinica, 2018, 46(11): 2679-2687.

参考文献

[1] Karamshuk D,Boldrini C,Conti M,et al.Human mobility models for opportunistic networks[J].Communications Magazine,IEEE,2011,49(12):157-165.
[2] 徐佳,孙力娟,王汝传,等。机会网络中基于种子喷雾的自适应路由协议[J].电子学报,2010,38(10):2315-2321. XU Jia,SUN Li-juan,WANG Ru-chuan,et al.Adaptive seed spray routing for opportunistic networks[J].Acta Electronica Sinica,2010,38(10):2315-2321.(in Chinese)
[3] 吴克军,于全,田艳霞.一种位置信息辅助的Ad Hoc网络按需距离矢量路由协议[J].电子学报,2010,38(4):983-988. WU Ke-jun,YU Quan,TIAN Yan-xia.A novel location-aided AD hoc on-demand vector routing protocol[J].Acta Electronica Sinica,2010,38(4):983-988.(in Chinese)
[4] Vahdat A,Becker D.Epidemic routing for partially connected ad hoc networks[R].CS-200006,Duke University,2000.
[5] Spyropoulos T,Psounis K,Raghavendra C S.Spray and wait:an efficient routing scheme for intermittently connected mobile networks[A].Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-tolerant networking[C].ACM,2005.252-259.
[6] Spyropoulos T,Psounis K,Raghavendra C S.Spray and focus:Efficient mobility-assisted routing for heterogeneous and correlated mobility[A].Pervasive Computing and Communications Workshops,2007.PerCom Workshops' 07.[C].IEEE,2007.79-85.
[7] Hanbali A A,Nain P,Altman E.Performance of ad hoc networks with two-hop relay routing and limited packet lifetime[A].Proceedings of the 1st International Conference on Performance Evaluation Methodolgies and Tools[C].ACM,2006:49.
[8] Burns B,Brock O,Levine B N.MV routing and capacity building in disruption tolerant networks[J].Ad Hoc Networks,2005,1(4):398-408.
[9] Lindgren A,Doria A,Schelén O.Probabilistic routing in intermittently connected networks[J].ACM SIGMOBILE Mobile Computing and Communications Review,2003,7(3):19-20.
[10] Hui P,Crowcroft J,Yoneki E.Bubble rap:Social-based forwarding in delay-tolerant networks[J].Mobile Computing,IEEE Transactions on,2011,10(11):1576-1589.
[11] Daly E M,Haahr M.Social network analysis for information flow in disconnected delay-tolerant MANETs[J].Mobile Computing,IEEE Transactions on,2009,8(5):606-621.
[12] Kim S,Gerla M.Socio-geo:Social network routing protocol in delay tolerant networks[A].Computing,Networking and Communications (ICNC)[C].IEEE,2016.1-6.
[13] 马学彬,白婧,郑田玉.机会网络中基于有权社团结构图的路由协议研究[J].电子学报,20164,(10):2449-2458. MA Xue-bin,BAI Jing,ZHENG Tian-yu.A routing algorithm based on weighted community detection for Opportunistic networks[J].Acta Electronica Sinica,2016,44(10):2449-2458.(in Chinese)
[14] Chaintreau A,Hui P,Crowcroft J,et al.Impact of human mobility on opportunistic forwarding algorithms[J].Mobile Computing,IEEE Transactions on,2007,6(6):606-620.
[15] Boldrini C,Conti M,Passarella A.Less is more:long paths do not help the convergence of social-oblivious forwarding in Opportunistic Networks[A].Proceedings of the third ACM International Workshop on Mobile Opportunistic Networks[C].ACM,2012.13-20.
[16] Boldrini C,Conti M,Passarella A.Performance modelling of opportunistic forwarding with imprecise knowledge[A].Modeling and Optimization in Mobile,Ad Hoc and Wireless Networks (WiOpt)[C].IEEE,2012.216-223.
[17] Boldrini C,Conti M,Passarella A.Performance modelling of opportunistic forwarding under heterogenous mobility[J].Computer Communications,2014,48:56-70.
[18] Boldrini C,Conti M,Passarella A.The stability region of the delay in Pareto opportunistic networks[J].IEEE Transactions on Mobile Computing,2015,14(1):180-193.
[19] Sermpezis P,Spyropoulos T.Delay analysis of epidemic schemes in sparse and dense heterogeneous contact environments[R].Eurecom,Biot,France,2012.3868.
[20] Picu A,Spyropoulos T,Hossmann T.An analysis of the information spreading delay in heterogeneous mobility dtns[A].World of Wireless,Mobile and Multimedia Networks (WoWMoM)[C].IEEE,2012.1-10.
[21] Ying L,Hong-Duo C,Xiu-Ming S,et al.An estimation formula for the average path length of scale-free networks[J].Chinese Physics B,2008,17(7):2327.
[22] Sermpezis P,Spyropoulos T.Delay analysis of epidemic schemes in sparse and dense heterogeneous contact networks[J].IEEE Transactions on Mobile Computing,2017,16(9):2464-2477.
[23] HaggleProject[OL]:https://crawdad.cs.dartmouth.edu/.
[24] 李旲,山秀明,任勇.具有幂率度分布的因特网平均最短路径长度估计[J].物理学报,2004,53(11):3695-3700. LI Ying,Shan Xiu-Ming,Ren Yong.Average path length of Internet with power law degree distribution[J].Acta Physica Sinica.2004,53(11):3695-3700.(in Chinese)

具有传输成功率保证的概率路由算法的TTL预测模型

The TTL Prediction Model of Probability Routing Algorithm with the Transmission Rate Guaranteed

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	崔苑茹, 李鹏, 刘宏, 王小明, 吴晓军. 基于校园机会网络的协作小组缓存调度策略[J]. 电子学报, 2021, 49(12): 2399-2406.
[2]	徐少平, 林珍玉, 张贵珍, 陈孝国, 李芬. 采用深度学习与图像融合混合实现策略的低照度图像增强算法[J]. 电子学报, 2021, 49(1): 72-76.
[3]	马学彬, 郑田玉, 李明珠. 机会网络中自私行为影响的分析与调节[J]. 电子学报, 2019, 47(4): 837-847.
[4]	王悦斌, 蒋景飞, 张建秋. 动态出现和/或消失时频信号的模型和分析[J]. 电子学报, 2019, 47(2): 495-501.
[5]	李鹏, 王小明, 张立臣, 卢俊岭, 朱腾蛟, 张丹. 机会网络视频数据的分块渐进传输新方法[J]. 电子学报, 2018, 46(9): 2165-2172.
[6]	舒坚, 张学佩, 刘琳岚, 杨志勇. 基于深度卷积神经网络的多节点间链路预测方法[J]. 电子学报, 2018, 46(12): 2970-2977.
[7]	潘海洋, 郑近德, 杨宇, 童宝宏. 基于CELCD和MFVPMCD的智能故障诊断方法研究[J]. 电子学报, 2017, 45(3): 546-551.
[8]	魏琳, 周磊, 吴宁, 杨睛. 多处理器片上系统中一种结合二阶导数的温度预测模型[J]. 电子学报, 2016, 44(6): 1272-1278.
[9]	刘春蕊, 张书奎, 贾俊铖, 林政宽. 机会网络中基于摆渡节点与簇节点相互协作的路由机制[J]. 电子学报, 2016, 44(11): 2607-2617.
[10]	马学彬, 白婧, 郑田玉. 机会网络中基于有权社团结构图的路由协议研究[J]. 电子学报, 2016, 44(10): 2449-2458.
[11]	巩萍, 程玉虎, 王雪松. 基于语义属性的肺结节良恶性分类[J]. 电子学报, 2015, 43(12): 2476-2483.
[12]	高志伟, 姚尧, 饶飞, 刘延钊, 罗平. 基于漏洞严重程度分类的漏洞预测模型[J]. 电子学报, 2013, 41(9): 1784-1787.
[13]	牛建伟, 戴彬, 孙利民, 林佳骝, 熊永平. PQBCF:一种基于中间中心度的机会网络P2P查询算法[J]. 电子学报, 2013, 41(9): 1815-1820.
[14]	徐佳;孙力娟;王汝传;刘凤玉. 机会网络中基于种子喷雾的自适应路由协议[J]. 电子学报, 2010, 38(10): 2315-2321.
[15]	马君;刘小冬;孟颖. 基于神经网络的城市交通流预测研究[J]. 电子学报, 2009, 37(5): 1092-1094.