摘要
近年来，无线网络通信技术得到了快速的发展，便携式、微型化计算设备迅速普及，基于无线网络的应用和服务在互联网服务中所占的比例逐年增大。越来越多的移动通信用户开始使用具有Wi-Fi或蓝牙功能的智能手机，PDA以及其他能够进行无线通信的网络设备，使得无线局域网普及率不断上升。无线网络技术与可接入网络的移动无线终端之间的结合开始变得越来越紧密、越来越成熟。另一方面，大多数用户使用便携的无线移动设备接入无线网络，使得无线网络中的节点所表现出的某些特性与人类社会行为特征极为相似。近年来，通过借助计算机技术，数学、图论的相关理论，社区网络的研究正在蓬勃发展。
因此，结合无线自组织网络的消息分发的特点和社区网络分析方法，本文从社区划分和消息分发策略两部分展开研究，旨在提高无线网络中消息的转发成功率和降低整个系统开销。根据对社区网络特征的研究，本文提出一种基于分割思想的社区划分算法，通过移除节点间的边来完成社区的划分过程。基于相似度的排序选取具有最小相似性的边作为移除边。社区划分完成后，再根据社区内节点移动性、连通度、缓存能力的权值序列为每个社区指定中心节点。
另一方面，通过携带转发策略进行数据转发的思路侧重于减少数据传输过程中的延迟而没有考虑网络带宽及用户端负载等因素对转发过程的影响，而根据兴趣度选择数据转发对象的方式虽然减少了数据在无关节点上的冗余，但在选择中间节点的过程中花费了一定时间从而导致数据的转发时延增大，因此本文提出的基于社区划分的消息分发方法对无线网络的消息分发过程进行了适当的改进，旨在缩短网络延迟和减少资源冗余，取得了一定的创新科研成果，核心内容如下：
（1）、简要介绍了社区网络的研究进展和应用领域，阐述了国内外对社区划分方法的研究进展以及无线自组织网络消息分发方法的研究现状以及存在的问题等。
（2）、归纳了无线自组织网络的定义及特点，介绍了目前无线自组织网络的应用领域及发展前景，详细介绍了社会网络理论模型及其应用，简要说明了车载无线自组织网络的概念特点和应用。
（3）、提出了基于聚类算法的社区划分方法，并引入多个参数共同动态选取每个社团的中心节点。在消息转发阶段，提出了改进的限制跳数的传染病路由协议和基于候选携带节点的“存储—携带—转发”方法。
（4）、利用ONE模拟仿真平台，本课题对本文提出的无线网络中基于社区的消息分发方法进行模拟仿真实验，同时对经典路由的传染病Epidemic算法、PROPHET算法以及等待转发Spray And Wait算法进行了仿真测试，对比和分析实验数据结果得出结论：在交付率、网络延迟以及节点缓存方面，本文提出的算法在总体上均优于EPI，PROPHET，SAW。
综上，本文针对基于社区划分的无线自组织网络的数据传输可靠性的提高和降低消息副本冗余，优化消息分发过程等关键问题提出了有效的解决方案，对于提高无线自组织网络的消息分发的可靠性和降低延迟有一定的改善，具有实际的理论意义和应用价值。
In recent years, wireless network communication technology has been rapid development.Portable and micro computing devices are rapidly growing popularity. The proportion ofwireless network-based applications and services in the Internet services is growing. With moreand more users start using the smart phone with Wi-Fi or Bluetooth, PDAs and mobile wirelessnetwork equipment and other mobile devices with wireless LAN access, wireless LANpenetration continues to rise. The connection between the wireless network technology and themobile wireless network terminal became more and more close and mature. Because most userscarry wireless mobile devices to access the wireless network, which makes the wireless networknodes have the characteristics of human social behavior. These years, researchers with the helpof computer technology, mathematics, graph theory makes the research of community networksboom.
Combined with the dates’distribution characteristics of wireless ad hoc networks andcommunity networks analysis methods, our research has proposed the community dividedmethod and the message distribution strategy. Designed to improve the wireless networkmessage forwarding success rate and reduce the overhead of the entire system. Research on thecharacteristics of community networks, our paper presents a community partitioning algorithmbased on the segmentation strategy: The edge of the minimum similarity will be removed basedon the similarity sorting. After the completion of community division, the system will specify thecentral node according to node mobility within the community, connectivity, the sequence of theweight of the cache capacity for each community.
On the other hand，the data delivery method using the carrying-and-forwarding strategy hasplaced extra emphasis on reduce the network delay and ignored Network bandwidth and clientload. The node selection method according interest has reduced the redundancy on independentnode, but because of it needed to select Intermediate node , this method cost a long delay. Ourpaper proposed a data forwarding method based on community division in wireless Ad hocnetwork. It aims to shorten network delay and reduce resource redundancy in data forwardingprocess. The core content is as follows:
（1）、Briefly introduced the research progress and applications of community network,described the progress of domestic and international research on the methods of communitydivision and the research status of wireless ad hoc network message distribution method and the existence of problems.
（2）、Summarized the definition and characteristics of wireless ad hoc networks, thecurrent applications and the development prospects of wireless ad hoc networks. Detailed themodel and its application of social network theory and explained the characteristics andapplications of the concept of car wireless ad hoc networks.
（3）Proposed the clustering algorithm based Community division method, and introducedmultiple parameters to dynamically select the central node of each community. On messageforwarding stage, proposed hops-limit epidemic routing protocol and candidate node based"storage - carry - forward" method.
（4）、Simulate the process of our data delivery method by ONE simulation platform andsimulate the Epidemic routing algorithm, the PROPHET and the Spray And Wait algorithm.After the comparison and analysis of experimental data we can reach a conclusion: the proposedalgorithm is superior to the EPI, PROPHET, SAW in delivery rate, network latency and nodecache.
In conclusion, the article provides effective solution to the key problem of improve thewireless network message forwarding success rate and reduce the overhead of the entire systemand has a certain theoretical meaning and application value in wireless ad hoc networks.
引文
[1] A. L. Barabasi, E. Bonabeau. Scale-Free Networks, 50-59. 2003,May
[2] M. E. J. Newman and M. Girvan.()Finding and evaluating community structure in networks. 2006,April.
[3] M. Musolesi and C. Mascolo. A Community Based Mobility Model for Ad Hoc Network Research.REALMAN’06, 2006, May ,26Florence, Italy.
[4] G. Palla, I.Derényi, I. Farkas , T.Vicsek. Uncovering the overlapping community structure of complexnetworks in nature and society. Nature 435, 814-818 (9 June 2005).
[5]熊永平,孙利民,牛建伟,等.机会网络[J].软件学报, 2009, 20(1): 124-137.
[6] A. Vahdat, D. Becker. Epidemic Routing for Partially-Connected Ad Hoc Networks. Technical ReportCS-200006，Duke University ,April 2000.
[7] S. Jain, K. Fall, and R. Patra. Routing in a Delay Tolerant Network. In Proc. of ACM SIGCOMM, 2004.
[8] H.Pan,J. Crowcroft,E. Yoneki.BUBBLE Rap:Socia-based forwarding in delay tolerant networks[c]/Procof the 9th ACM Int Symp on Mobile Ad Hoc Networking and Computing.New York,ACM,2008,241-250.
[9] M. E. J. Newman and M. Girvan .Finding and evaluating community structure in networks. PHYSICALREVIEW E 69, 026113 2004.
[10] F. Li and J. Wu, MOPS: Providing Content-based Service in Disruption-tolerant Networks, Proc. Of the29th International Conference on Distributed Computing Systems (ICDCS), 2009.
[11] S. Corson,J.Macker. Mobile Ad Hoc Networking(MANET):Routing Protocol Performance Issues andEvaluation Considerations[EB/01] .IETF RFC250,http://www.ietf.org/rfc/rfc2501.txt,1999txt，1999
[12]唐伟，郭伟．无线传感器网络中的最大生命期基因路由算法[J]．软件学报，2010，21(7)：1646-1656．
[13] S.Wasserman, K.Faust.Social Network Analysis: Methods and Applications[M]. New York:Cambridge University Press,1994.
[14]刘军.社会网络分析导论.北京:社会科学文献出版社, 2004,45-56.
[15] L.C. Freeman. A set of measures of centrality based upon betweenness[J].Sociometry,1977, 40:35-41.
[16] A. Barrat, M. Weigt. On the properties of small-world networks[J].European PhysicalJournalB,2000,13(3):547–560.
[17] D.J. Watts, S.H. Strogatz. Collective dynamics of small-worldnetworks[J].Nature,1998,393(6684):440–442.
[18]张星，夏火松，蔡淑琴，企业内部社会网络的市场机遇信息角色研究，情报杂志，Dec.2009,Vo1.28，No.12.
[19]杨莉莉，杨永川，基于社会网络的犯罪组织关系挖掘，计算机工程，August 2009, Vol.35，No.15.
[20] W. J.Hsu and A. Helmy, On Nodal Encounter Patterns in Wireless Lan Traces, in Proceedings of SecondWorkshop on Wireless Network Measurements (WiNMee 2006), 2006
[21] E.Daly ,M. Haahr, Social Network Analysis for Routing in Disconnected Delay-Tolerant MANETs, Inproceeding of MobiHoc’07,September,2007,Montréal,Québec,Canada.
[22] B.Fiebig. European traffic accidents and Purposed solutions.2003 ITU-T Workshop on Standardizationin Telecommunication for Motor Vehicles, Vol.1:24-25.
[23] Dedicated Short Range Communications home，http://www. ieearmstrong.com/dsrc.
[24] Wireless Access in Vehicular Environments. http://www.ieee802.org/11/Reports.
[25] W.Franz, R. Eberhardt, T. Luckenbach. Fleetnet-Internet in the road. 2001 World Congress on IntelligentTransportation Systems,Vol.1:27-38.
[26] NOW: Network on wheels，http://www.network-onwheels.de.
[27]常促宇，向勇，史美林.车载自组网的现状与发展[J].通信学报，2007，11.
[28] S. Yousefi, S.M. Mahmoud, F. Mahmood. Vehicular Ad Hoc Networks(VANETs):Challenges andPerspectives[C].2006 6th International Conference on ITS Telecommunications Proceedings,2006:761-766.
[29] N.Wisitpongphan,F. Bai.On the routing Problem in disconnected vehicular ad hoc networks.2007IEEEInternational Conference on Computer Communications(INFOCOM`07),Vol.1:67-78.
[30] M. Rudack, M. Meincke, M.Lott. On the dynamics of ad hoc networks for inter vehicle communication(IVC).2002 International Conference on Wireless Networks (ICWN`02),Vol.2:655-663.
[31] S. Y. Ni, Y.C. Tseng. The broadcast storm problem in a mobile ad hoc network.1999 ACM/IEEEInternational Conference. on Mobile Computing and Networking, Vol.1:152-162.
[32] Jaehoon Jeong. Wireless Sensor Networking for Intelligent Transportation Systems.
[33] Jing Zhao and Guohong Cao. VADD: Vehicle-Assisted Data Delivery in Vehicular Ad Hoc Networks.IEEE Transactions on Vehicular Technology, 57(3):1910–1922, May 2008.
[34] Afra J. Mashhadi, Sonia Ben Mokhtar and Licia Capra. Habit: Leveraging Human Mobility and SocialNetwork for Efficient Content Dissemination in MANETs.
[35] Ari Ker nen, J rg Ott, Teemu K rkk inen. The ONE simulator for DTN Protocol Evaluation: Proc. ofthe 2nd International Conference on Simulation Tools and Techniques[C]. [ S. l. ] : [s.n.],2009.
[36] TKK/COMNET. Project page of the ONE simulator [EB/OL].http://www.netlab.tkk.fi/tutkimus/dtn/theone, 2008.
[37] T. Spyropoulos, K. Psounis,C. S. Raghavendra, Efficient Routing in Intermittently Connected MobileNetworks: The Multiple-copy Case,IEEE/ACM Transactions on Networking, 2008.
[38] E. Bulut, Z. Wang, B. Szymanski Cost Effective Multi-Period Spraying for Routing in Delay TolerantNetworks, to appear in IEEE/ACM Transactions on Networking, 2010.
[39] J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine, MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks, Proc. IEEE Infocom,April 2006.
[40] E.Bulut, Z.Wang, B. Szymanski, Cost Efficient Erasure Coding based Routing in Delay TolerantNetworks, Proc. ICC 2010.
[41] Kyunghan Lee (KAIST), Seongik Hong (NCSU), Seong Joon Kim (NCSU),Injong Rhee (NCSU) andSong Chong (KAIST), SLAW: A Mobility Model for Human Walks, IEEE Communications Society subjectmatter experts for publication in the IEEE INFOCOM 2009.
[42]王硕，王新华，刘婧，刘永．一种基于社区划分的数据分发方法[J]．计算机技术与发展，2011,21(10),210-213.
[43]牛建伟，周兴，刘燕，孙利民,马建一种基于社区机会网络的消息传输算法[J]计算机研究与发展,2009. 46(12).