一种适用于移动对等网络的分簇算法

J4 ›› 2014, Vol. 36 ›› Issue (07): 1268-1274.

一种适用于移动对等网络的分簇算法

杨忠仪1,2，左克1

(1.国防科学技术大学计算机学院,湖南长沙 410073;2.湖南商务职业技术学院,湖南长沙 410205)

收稿日期:2013-01-21 修回日期:2013-05-10 出版日期:2014-07-25 发布日期:2014-07-25
基金资助:
国家863计划资助项目（2012AA010903）

A clustering algorithm for
mobile peer-to-peer network

YANG Zhongyi1,2,ZUO Ke1

(1.College of Computer,National University of Defense Technology,Changsha 410073;
2.Hunan Vocational College of Commerce,Changsha 410205,China)

Received:2013-01-21 Revised:2013-05-10 Online:2014-07-25 Published:2014-07-25

摘要/Abstract

摘要：

通过分簇算法减小网络振动效应，延长网络的寿命是移动对等网络的研究重点之一。在研究Kautz图及其特性的基础上，提出一种基于Kautz图的移动对等网络分簇算法。在算法中，定义地址空间树，使用Kautz串作为节点标识，并运用后根序和宽度优先算法遍历地址空间树等一系列技术生成簇。同时设计了相关机制管理和维护簇结构，保证结构一致性。理论证明和实验评估表明，该分簇算法能有效减小振动效应，延长网络寿命。

关键词: Kautz图, 分簇算法, 移动对等网络

Abstract:

Using the clustering algorithm to reduce the network churn effect and extend the network lifetime is one of the research emphasis points of mobile peer-to-peer networks. Based on studying the Kautz graph and its characteristics, a clustering algorithm of mobile peer-to-peer network based on the Kautz graph is proposed. In the algorithm, an address space tree is defined firstly, and then the Kautz string is used as nodes’ identifier. The breadth-first-search via post-order is used to travel a well-defined address tree for clusters creation. Besides, the mechanism for management and maintenance of cluster structure is designed to ensure the structural integrity. Theoretical proof and experimental evaluation show that the clustering algorithm can effectively reduce the churn effect and extend the network lifetime.

Key words: Kautz graph;clustering algorithm;mobile peer-to-peer network

杨忠仪1,2，左克1. 一种适用于移动对等网络的分簇算法[J]. J4, 2014, 36(07): 1268-1274.

YANG Zhongyi1,2,ZUO Ke1. A clustering algorithm for
mobile peer-to-peer network [J]. J4, 2014, 36(07): 1268-1274.

参考文献

［1］Zhang Shile, Wei Fang, Fei Zhongchao. Study on architecture of video transmission optimisation on mobile internet［J］. Computer Applications and Software,2012,29(4):106108. (in Chinese)
［2］Ni Ping, Wei Fang. A method for improving data pattern readability in wireless sensor networks［J］. Computer Applications and Software, 2012,29(10):148151. (in Chinese)
［3］Chen Guihai,Li Hongxing,Han Song,et al.Network codingaware multipath routing in multihop wireless networks［J］. Journal of Software,2010,21(8):19081919. (in Chinese)
［4］Pucha H, Das S M, Hu Y C. Imposed route reuse in ad hoc network routing protocols using structured peertopeer overlay routing［J］. IEEE Transactions on Parallel and Distributed Systems, 2006,27(12):14521467.
［5］Hu Y C, Das S M, Pucha H. Exploiting the synergy between peertopeer and mobile ad hoc networks［C］∥Proc of Workshop on Hot Topics in Operating Systems, 2003:3742.
［6］Pucha H, Hu Y C. Ekta:An efficient DHT substrate for distributed applications in mobile ad hoc networks［C］∥Proc of the 6th IEEE Workshop on Mobile Computing Systems and Applications, 2004:163173.
［7］Hu Y C, Das S M, Pucha H. Peertopeer overlay abstractions in MANETs［C］∥Proc of the 1st International Workshop on Decentralized Rosoune Sharing in Mobile Computing Networking, 2004:845864.
［8］Gerla M, Lindemann C, Rowstron A. P2P MANETsNew research issues［M］∥Perspectives Workshop:PeertoPeer Mobile Ad Hoc Networks, TX:IBFI Press, 2005.
［9］Caesar M, Castro M, Nightingale E B, et al. Virtual ring routing:network routing inspired by DHTs［C］∥Proc of SIGCOMM’11, 2011:351362.
［10］Miller M, Siran J. Moore graphs and beyond:A survey of the degree/diameter problem［J］. Electronic Journal of Combinatorics, 2005,61:163.
［11］Zhang Yiming. Distributed line graphs:A universal technique for designing DHTs based on arbitrary regular graphs［J］. IEEE Transactions on Knowledge and Data Engineering, 2013,24(9):15561569.
［12］Feng Huang. Fast data dissemination in Kautzbased modular datacenter network［C］∥Proc of 2012 International Conference on Systems and Informatics (ICSAI), 2012:16061610.
［13］Banerjee S, Khuller S. A clustering scheme for hierarchical control in multihop wireless networks［C］∥Proc of INFOCOM’01, 2001:10281037.
［14］Baker D J, Ephremides A. The architectural organization of a mobile radio network via a distributed algorithm［J］. IEEE Transactions on Communications, 1981,29(1):16941701.
［15］Baker D J, Wieselthier J, Ephremides A. A distributed algorithm for scheduling the activation of links in a selforganizing, mobile, radio network［C］∥Proc of IEEE ICC’82, 1982:1.
［16］Gerla M, Tsai J TC. Multicluster, mobile, multimedia radio network［J］. Journal of Wireless Networks, 1995,1(3):255265.
［17］Ns2 network simulator［EB/OL］.［20130516］.http://www.isi.edu/nsnam/ns/.
［18］The VRR Windows XP implementation［EB/OL］.［20130516］.http://research.microsoft.com/vrr/.
［19］Yu C, Shin K G, Lee B, et al. Node clustering in mobile peertopeer multihop networks［C］∥Proc of IEEE International Conference on Pervasive Computing and Communications, 2006:130134.
［20］Zahn T, Schiller J. MADPastry:A DHT substrate for practicably sized MANETs［C］∥Proc of the 5th Workshop on Applications and Services in Wireless Networks, 2009:1.
［21］Yoneki E, Bacon J. Dynamic group communication in mobile peertopeer environments［C］∥Proc of the 20th Annual ACM Symposium on Applied Computing,2005:986992.
［22］Eriksson J,Faloutsos M,Krishnamurthy S.PeerNet:Pushing peertopeer down the stack［C］∥Proc of IPTPS’03, 2003:268277.
［23］Pucha H, Das S M, Hu Y C. Imposed route reuse in ad hoc network routing protocols using structured peertopeer overlay routing［J］. IEEE Transactions on Parallel and Distributed Systems, 2006,17(12):14521467.
附中文参考文献：
［1］张世乐魏芳费仲超. 移动互联网视频传输优化的架构研究［J］. 计算机应用与研究，2012,29(4):106108.
［2］倪萍魏芳.一种提高无线传感网络数据模式可读性的方法［J］. 计算机应用与研究，2012,29(10):148151.
［3］陈贵海,李宏兴,韩松,等.多跳无线网络中基于网络编码的多路径路由［J］. 软件学报，2010,21(8):19081919.

[1]	左克，吴泉源，胡东敏. 移动对等网络支撑平台MOBIPEER的设计与实现[J]. J4, 2012, 34(12): 27-33.
[2]	蒋文斌1，余林琛1, 2，廖光贤1，廖小飞1，王鹏程1，陈珍1. 移动对等直播流媒体系统的服务质量保证机制研究[J]. J4, 2012, 34(10): 11-16.
[3]	王宇科1，黎文伟2，苏欣2. 基于改进分簇算法的网络流量识别方法[J]. J4, 2011, 33(11): 10-14.
[4]	林要华, 胡华平,. 基于轨道预测的自适应Ad Hoc分簇算法[J]. J4, 2010, 32(2): 27-30.
[5]	吴迪胡钢倪刚张卓李威. 无线传感器网络多路径簇头链分簇式路由算法[J]. J4, 2008, 30(6): 101-105.
[6]	胡光明蒋杰龚正虎. 移动自组网络分簇算法综述[J]. J4, 2005, 27(1): 48-50.