摘要
近些年来随着无线网络技术的成熟和智能便携节点的普及,时滞容忍网络的研究和应用迅速发展起来。这类网络不受网络结构的限制,充分利用移动设备的带宽、计算、存储等资源,通过各种连接途径为用户提供数据传输、数据分发、信息查询等网络服务。由于时滞容忍网络组网方便,不需要额外的基站设备,因此具有广泛的应用前景,对未来普适计算的实现具有深远的影响。
时滞容忍网络在实际应用中存在网络拓扑动态变化、传输带宽受限、移动终端受限等一系列问题。尽管之前的研究者在这些方面已经做了大量的研究,但是大部分模型只适用于特定的场景,算法的传输性能和稳定性能也有待提高。针对上述问题,本文借鉴传统网络的研究方法,对时滞容忍网络进行了全面的分析和研究,主要有如下贡献：
基于真实环境中收集到的数据,从实验的角度分析了节点之间接触情况和时滞容忍网络中社区与地理位置的关系,提出了地理社区的概念,并重点研究了体现网络连通特性的节点接触间隔时间分布和节点在社区的滞留时间分布,为之后的建模打下基础。
将节点在社区之间的移动看作马尔科夫过程,使用单步转移概率和滞留时间概率构建节点移动静态模型,通过模型得到反映节点和社区接触的静态分布概率和社区中心度,解决时滞容忍网络中的数据分发问题。使用时间相关单步转移概率和条件滞留时间概率构建节点移动动态模型,通过模型得到反映节点移动轨迹的瞬时分布概率,解决时滞容忍网络中的信息查询问题。
通过历史记录数据来预测自身和邻居节点在未来不同时刻的相遇概率,并引入了节点效用值,在此基础上设计了时滞容忍网络的自适应异步休眠机制。该机制有效地提高了节点能量的利用率,并能够兼容现有的数据传输算法。
Recently, with the maturation of wireless network technology and the popularity of smart portable nodes, researches and application on Delay Tolerant Networks(DTNs) are developing rapidly. Not limited by the network structure, DTNs make full use of portable devices'bandwidth, computing, storage and other resources, and provide users with data transmission, data dissemination, information query and other network services via a variety of connecting ways. Since DTNs need no additional base station devices to form the network, they have wide application prospects and far-reaching impacts on the realization of future pervasive computing.
There exist a lot of problems in the practical application of Delay Tolerant Networks, for example:dynamic changing of the network topology, the limitation of the transmission bandwidth, the limitation of the portable terminals and so on. Although previous researchers have done a lot in these areas, most models are only suitable for specific scenarios, and the transmission and stability performance of algorithms need to be improved. To address the above issues, this paper conducts a comprehensive analysis and research in DTNs on the basis of drawing on the research methods in the traditional network. The main contributions are as follows:
Based on data traces collected from the real environment, we experimentally investigate the pair-wise contact information and the correlation of community and geography information. Then, we propose the concept of geography-aware community (Geo-community) and analyze the distribution of the inter-contact time and the user sojourn time distribution over geo-communities,both of which characterize the network connectivity features. This work lays a foundation for modeling.
By considering the user mobility among different communities as a Markov renewal process, we use the single-step transition probability and sojourn time probability to build nodes'static mobility model, and get the static distribution probability and geo-centrality which reflect the contact between nodes and community, so as to solve the data dissemination problem in DTNs. Furthermore, we use the temporal correlation single-step transition probability and conditional sojourn time probability to build nodes' dynamic mobility model, obtaining the instantaneous distribution probability which reflects the movement locus of nodes, so as to solve the information query problem in DTNs.
Using the past recorded information to predict the future contact information with other neighbors and introducing the value of node utility, an adaptive asynchronous sleep scheduling mechanism is proposed for DTNs. The propose sleep scheduling mechanism can improve the energy efficiency effectively, and is compatible with existing data transmission protocols.
引文
[1]C.E. Perkins, and E.M. Royer. Ad-hoc on-demand distance vector routing. IEEE WMCSA,1999,90-100.
[2]D.B. Johnson, D.A. Maltz, and J. Broch. DSR:The dynamic source routing protocol for multi-hop wireless ad hoc networks. Ad hoc networking,2001,5:139-72.
[3]K. Fall. A delay-tolerant network architecture for challenged internets. ACM SIGCOMM,2003,27-34.
[4]J. Kleinberg. The small-world phenomenon:an algorithm perspective. ACM STOC,2000,163-170.
[5]P. Juang, H. Oki, Y. Wang, M. Martonosi, L.S. Peh, and D. Rubenstein. Energy-efficient computing for wildlife tracking:Design tradeoffs and early experiences with zebranet. ACM Sigplan,2002,37:96-107.
[6]T. Small, and Z.J. Haas. The shared wireless infostation model:a new ad hoc networking paradigm (or where there is a whale, there is a way). ACM MobiHoc, 2003,233-244.
[7]P. Hui, A. Chaintreau, J. Scott, R. Gass, J. Crowcroft, and C. Diot. Pocket switched networks and human mobility in conference environments. ACM WDTN, 2005,244-251.
[8]A.K. Pietilainen, and C. Diot. Social pocket switched networks. IEEE INFOCOM, 2009,1-2.
[9]B. Hull, V. Bychkovsky, Y. Zhang, K. Chen, M. Goraczko, A. Miu, E. Shih, H. Balakrishnan, and S. Madden. CarTel:a distributed mobile sensor computing system. ACM SenSys,2006,125-138.
[10]M. Conti, and S. Giordano. Multihop ad hoc networking:The reality. IEEE Communications Magazine,2007,45(4):88-95.
[11]熊永平,孙利民,牛建伟,刘燕.机会网络.软件学报,2009,20(1)：124-37.
[12]M. Mcnett, and G.M. Voelker. Access and mobility of wireless PDA users. ACM SIGMOBILE Mobile Computing and Communications Review,2005,9(2):40-55.
[13]N. Eagle, and A. Pentland. Reality mining:sensing complex social systems. Personal and Ubiquitous Computing,2006,10(4):255-68.
[14]J.K. Lee, and J.C. Hou. Modeling steady-state and transient behaviors of user mobility:formulation, analysis, and application. ACM MobiHoc,2006,85-96.
[15]A. Peddemors, H. Eertink, and I. Niemegeers. Predicting mobility events on personal devices. Pervasive and Mobile Computing,2010,6(4):401-23.
[16]A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott. Impact of human mobility on opportunistic forwarding algorithms. IEEE Transactions on Mobile Computing,2007,6(6):606-20.
[17]M. Piorkowski, N. Sarafijanovic-Djukic, and M. Grossglauser. CRAWDAD data set epfl/mobility (v.2009-02-24).
[18]H. Zhu, L. Fu, G. Xue, Y. Zhu, M. Li, and L.M. Ni. Recognizing exponential inter-contact time in VANETs. IEEE INFOCOM,2010,1-5.
[19]J. Broch, D. B. Johnson, and D. A. Maltz. The dynamic source routing protocol for mobile ad hoc networks. Internet-Draft, draft-ietf-manetdsr-01.txt, work-in-progress,1998.
[20]C. Bettstetter, H. Hartenstein, and X. Prez-Costa. Stochastic properties of the random waypoint mobility model. Wireless Networks,2004,10(5):555-67.
[21]A.P. Jardosh, E.M. Belding-Royer, K.C. Almeroth, and S. Suri. Real-world environment models for mobile network evaluation. IEEE Journal on Selected Areas in Communications,2005,23(3):622-32.
[22]J.Y. LeBoudec, and M. Vojnovic. The random trip model:stability, stationary regime, and perfect simulation. IEEE/ACM Transactions on Networking (TON),2006, 14(6):1153-66.
[23]W. Gao, Q. Li, B. Zhao, and G. Cao. Multicasting in delay tolerant networks:a social network perspective. ACM MobiHoc,2009,299-308.
[24]T. Karagiannis, J.Y. LeBoudec, and M. Vojnovic. Power law and exponential decay of intercontact times between mobile devices. IEEE Transactions on Mobile Computing,2010,9(10):1377-90.
[25]P. Hui, J. Crowcroft, and E. Yoneki. Bubble rap:social-based forwarding in delay tolerant networks. ACM MobiHoc,2008,241-250.
[26]M. Musolesi, and C. Mascolo. A community based mobility model for ad hoc network research. ACM REALMAN,2006,31-38.
[27]T. Spyropoulos, K. Psounis, and C.S. Raghavendra. Performance analysis of mobility-assisted routing. ACM MobiHoc,2006,49-60.
[28]W.J. Hsu, T. Spyropoulos, K. Psounis, and A. Helmy. Modeling spatial and temporal dependencies of user mobility in wireless mobile networks. IEEE/ACM Transactions on Networking,2009,17(5):1564-77.
[29]A. Vahdat, and D. Becker. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University,2000.
[30]T. Spyropoulos, K. Psounis, and C.S. Raghavendra. Spray and wait:an efficient routing scheme for intermittently connected mobile networks. ACM WDTN,2005, 252-259.
[31]T. Spyropoulos, K. Psounis, and C.S. Raghavendra. Efficient routing in intermittently connected mobile networks:the multiple-copy case. IEEE/ACM Transactions on Networking,2008,16(1):77-90.
[32]T. Spyropoulos, K. Psounis, and C.S. Raghavendra. Efficient routing in intermittently connected mobile networks:The single-copy case. IEEE/ACM Transactions on Networking,2008,16(1):63-76.
[33]J. Widmer, and J.Y. LeBoudec. Network coding for efficient communication in extreme networks. ACM WDTN,2005,284-291.
[34]W. Zhao, M. Ammar, and E. Zegura. A message ferrying approach for data delivery in sparse mobile ad hoc networks. ACM MobiHoc,2004,187-198.
[35]J. Wu, S. Yang, and F. Dai. Logarithmic store-carry-forward routing in mobile ad hoc networks. IEEE Transactions on Parallel and Distributed Systems,2007,18(6): 735-48.
[36]W. Wang, V. Srinivasan, and M. Motani. Adaptive contact probing mechanisms for delay tolerant applications. ACM MobiCom,2007,230-241.
[37]S. Qin, G. Feng, and Y. Zhang. How the Contact-Probing Mechanism Affects the Transmission Capacity of Delay-Tolerant Networks. IEEE Transactions on Vehicular Technology,2011,60(4):1825-34.
[38]O. Trullols-Cruces, J. Morillo-Pozo, J.M. Barcelo-Ordinas, and J. Garcia-Vidal. Power Saving Trade-offs in Delay/Disruptive Tolerant Networks. IEEE WoWMoM, 2011,1-9.
[39]J. Fan, Y. Du, W. Gao, J. Chen, and Y. Sun. Geography-aware active data dissemination in mobile social networks. IEEE MASS,2010,109-118.
[40]J. Fan, J. Chen, Y. Du, P. Wang, and Y. Sun. DelQue:A Socially-Aware Delegation Query Scheme in Delay Tolerant Networks. IEEE Transactions on Vehicular Technology,2011,60(5):2181-2193.
[41]L.M. Feeney, and M. Nilsson. Investigating the energy consumption of a wireless network interface in an ad hoc networking environment. IEEE,2001,3:1548-1557.
[42]M. Stemm, R.H. Katz. Measuring and reducing energy consumption of network interfaces in hand-held devices. IEEE Transactions on Communications,1997,80(8): 1125-31.
[43]N. Banerjee, M.D. Corner, B.N. Levine. Design and field experimentation of an energy-efficient architecture for DTN throwboxes. IEEE/ACM Transactions on Networking,2010,18(2):554-67.