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

杨忠仪，左 克

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

1 引言

硬件技术的快速发展使得移动终端体积更小、更便携、续航能力更强;同时,无线通信带宽和范围的增长，使得原本为有线网络设计运行的应用能够逐渐部署运行在无线网络中。上述变革为移动对等网络MP2P(Mobile Peer-to-Peer)的存在和发展提供了可能[1～7]。

然而，移动网络的振动性给MP2P网络的网络寿命及其路由性能带来了挑战。图1描述了节点移动对路由产生的影响。图中有三个移动节点A、B、C。箭头指出节点的移动方向，圆圈范围表示节点的有效通讯范围。节点移动之前的路由情况如图1a所示，从节点A到节点C存在两条有效路由：多跳路由A-B-C或者一跳路由A-C；节点移动之后的路由情况如图1b所示，从节点A到节点C的有效路由只有多跳路由A-B-C。因此，需要设计一个高效的分簇算法，不但能够在MP2P网络中快速部署，还要有效管理、维护移动节点组织结构，敏捷反映MP2P网络拓扑结构的变化，延长网络寿命。

Figure 1 Challenges of the MP2P network performance stability opposed by node mobility图1 节点移动性给MP2P网络性能稳定性带来挑战

层次性结构(Hierarchical Architecture)作为一种经典有效的节点组织方式，被广泛使用在构造大规模移动网络节点组织上；同时，分簇算法(Clustering)被认为是一种有效的处理网络寿命的机制。当前MP2P网络中广泛使用分层管理机制来设计分簇算法[5,7,8]，研究人员通常根据已有的无线网络类型和结构化P2P抽象覆盖网络来设计MP2P系统以及节点管理机制[4,6,9]。近年来，Kautz图[10,11]及其特殊的属性，诸如优化的网络直径、高效路由特性、较好的连通性和低拥塞等特性逐渐吸引MP2P研究者的注意，思考如何将这些优秀的特性应用到MP2P这类计算和带宽资源均受限的特定环境中[11～13]；同时，以Kautz图为原理开发的路由协议和应用系统不断涌现，例如，使用MP2P构造的文件共享系统，能够充分利用各个移动终端的数据和存储资源，在无线和移动网络上节点之间根据对不同数据类型的需求以及地理位置信息的不同进行文件的直接共享和交换，实现灵活高效的数据共享，典型系统包括Google Open Spot和Nokia PeerBox 。此外，在开放环境(如在校园、野外、战地和受灾地区等缺乏固定通信基础设施的环境)中利用MP2P技术实现高效快捷的文件发布和共享，也是当前重要的应用，如Stanford校园Fring系统。

在本文中，我们基于Kautz图及其特性设计了一个有效的分簇算法，并结合网络路由协议VRR(Virtual Ring Routing)[9]进行了实现和验证。本文的主要贡献有：首先，依据Kautz空间，定义了可扩展的地址空间树和节点Kautz串标识符；接着我们给出了分簇算法并理论证明了该算法的有效性，算法使用后根序和宽度优先搜索算法遍历地址空间树，通过理论证明了设计的算法能够满足层次性结构需要的特性；第三，设计了分簇算法管理和维护机制，以应对网络振动问题；最后，通过路由协议验证和评估了分簇算法的有效性。

2 定义与定理

2.1 Kautz图和地址树

首先，给出Kautz图的定义。

由Kautz图的定义可知，其节点数接近Moore边界[10]，最多可由N=dD+dD+1个节点构成。另外，相比其他图，Kautz图还具有某些特性，诸如网络直径较短、有容错和负载平衡能力等。所有这些特性使得P2P网络的设计者更多倾向于使用Kautz图作为构造P2P网络的图论基础。下面根据Kautz串定义地址空间和地址树。

定义2假设T(d,D)代表Kautz图K(d,D)的地址树，从上至下T(d,D)共分D+1层，其中只有第0层的根节点有d+1个子节点，树中的其他节点只有d个子节点。从节点u到子节点的边从非负整数集{0,1,…,d}选择标记，按照从左至右增序排列，并且要求标记序列中没有重复标记。因此，除了根节点标记为null，每个节点标记是由从根节点到自身的边的标记组成的标记串，即Kautz串。地址空间树的所有叶节点的Kautz串，代表实际的空间地址集合。

图2给出K(2,3) 和对应的地址空间T(2,3)。图2中，节点A的标记是[010]，节点B的标记是[021]，节点C的标记是[x1x]，节点D的标记是[20x]，x代表尚未确定，当节点最终加入到地址树叶节点后，x才会被确定。具体的节点加入过程将在第3.2.1节和第3.2.2节中详细给出。

Figure 2 K(2,3)and space address tree of T(2,3)图2 K(2,3)和对应的地址空间T(2,3)

2.2 分簇算法

我们的算法实现在VRR(Virtual Ring Routing)[9]路由协议之上。作为第一个采用DHT(Distributed Hash Table)特点设计的网络层路由协议，VRR根据随机产生的非负整数标志，将节点组织成一个虚拟环。而且，VRR中没有设计网络协议普遍采用的泛洪(Flooding)算法，因此VRR能够获得比其他路由协议更好的性能。

为了设计分簇算法，需要对VRR进行两方面的修改。首先，我们使用Kautz地址空间中的节点标识替代VRR中随机产生的非负整数标识；第二，我们需要在路由表中添加一个标识位flag，以标注簇首。大多数移动网络中的分层cluster结构普遍采用簇首[14～16]设计。我们的算法中，指定节点标识K(d,D)的数值大小最接近MooreBound/2的节点作为簇首。 簇首节点负责存储cluster内所有节点信息，同时cluster内每个节点会在自己的路由表中标注簇首节点为ch_flah。

算法的执行过程就是寻找Kautz图K(d,D)中扩展树的过程。通过后根序和宽度优先算法遍历地址树T(d,D)的方式，我们将Kautz图中的所有节点进行分簇。在算法的执行过程中，必须保证标识数值大小接近的节点被分在同一个簇内，以便于之后快速构造虚拟环。下面列出了算法中使用的简写以及含义：

(1)非负整数k：用来约束每个簇的大小。考虑到负载平衡和容错，产生的所有簇的大小必须能够产生有效的路由。因此，我们设计最小的簇的大小等于最大簇的大小的一半。

(2)T：Kautz图K(d,D)对应的地址空间树。

(3)T(x)：T的子树，节点x作为子树的根节点。

(4)Q：队列类型的数据结构，用于存储簇中的节点。采用队列类型数据结构而非其他数据结构，因为我们不但需要使用队列的FIFO方式保存节点信息，而且还可以为之后构造虚拟环带来便利。

(5)C：队列型数据结构，用于合并分簇。

(6)ClusterSet：算法产生的簇集合。

(7)UnpChildren：存储某个节点尚未被分到某个簇中的所有子节点。

(8)PartialClusterSet：存储当前大小小于k的分簇集合。

(9)∅：表示空集合。

下面的伪代码对算法进行了详细的描述:

算法1Kautz-based Clutering (K,k)

1 foru∈K, in post-order travel ofT

2 if (|T(u)|≥k) then

3Q:=∅;

4UnpChildren:=Children(u);

5 whileUnpChildren≠∅ and (∃v∈UnpChildren,s.t.xhas an edge tow∈Children(u)∩Q) do

6 Enqueue nodes ofT(v)inQby the order from large to small and mark the one whose identifier is closest toMooreBound/2ofK(d,D)as clusterhead;

7 RemovevfromUnpchildren;

8 end while

9 if(|Q|≥k)then

10 OrganizeQas a virtual ring;

11ClusterSet:=ClusterSet∪Q;

12 Remove all substrees inQ;

13 else

14PartialClusterSet:=PartialClusterSet∪Q;

15 end if

16C:=MergeParticalClusterSet(u,k,PartialClusterSet,Q);

17 ifChildren(u):=∅ and (uhas been assigned to some cluster) then

18 Removeufrom the tree;

19 end if

20 end if

21ClusterSet:=ClusterSet∪C;

22 end for

算法2MergePartialClusterSet(u,k,P,ClusterSet)

1C:=∅;

2 While (P≠∅) do

3 Pick an arbitrary partial clusterpfromP;

4C:= orderly sorting nodes inCandpin the same order ofC;

5 RemovepfromP;

6 if (|C|≥k)then

7ClusterSet:=ClusterSet∪{C∪{u}};

8 Remove all subtrees inC;C:=∅;

9 end if

10 end while

2.3 算法属性证明

本节我们形式化证明算法的特性，这些特性为之后在实验评估中取得较好的测试结果提供了理论证明。

定理1算法保证所有节点都会被分配到某个簇中。

证明对任意节点u，如果u属于某个子树，则算法1的第4行保证他的所有子节点都已经被分配到UnpChildren。UnpChildren中所有子树的节点会被保存在队列Q中，算法1的第11行保证Q中的每个节点最终被分配到某个簇中。证毕。

□

定理2算法保证每个簇中节点会被组织成一个逻辑环。

证明根据算法1的第6、第10行，可以得到该属性。数据结构队列Q保证了该属性的实现。证毕。

□

定理3算法保证任意两个分簇之间只有一个公共节点。

证明我们采用反证法。如果存在两个公共节点，则根据Kautz图K(d,D)，这两个簇不可能同时存在于一个地址空间树T(d,D)中，因此定理3成立。证毕。

□

定理4算法保证只可能有一个簇的大小小于k，其他所有簇的大小介于k和2k之间。

证明算法1的第10～第16行中，ClusterSet中的簇大小均大于或等于k；同时PartialClusterSet中的簇大小小于k。如果存在两个簇的大小小于k，则他们将会在算法2的第6行中被合并，因此只可能有一个簇的大小小于k，其他所有簇的大小介于k和2k之间。

对P中的任意簇p，如果算法1第10行没有满足条件，则其大小小于或等于k-1。算法2中，簇会被合并成大小为2(k-1)-1=2k-1，仍然小于2k，因而定理4成立。证毕。

□

2.4 算法收敛性分析

为分析算法1的收敛性，我们先分析算法2的收敛性。算法2的第3行、第4行和第7行的执行为常数时间，第5行和第8行时间较少可忽略，因此算法2的时间收敛性主要依赖于P的大小，也就是PartialClusterSet的大小。因此，算法2的时间收敛性为O(n)。

算法1的收敛性的分析如下：从算法的伪代码可知，算法的收敛性主要取决于第6行和第10行，其中第10行的收敛性由VRR得知是O(n/(rp))，其中，n为节点数，r是移动终端通信半径，p是路由长度；算法的第6行约束p的大小为MooreBound/2ofK(d,D)，而d和D均小于或等于n。因此，我们设计的路由协议相比VRR而言，收敛性更好。

3 算法的实现

3.1 簇的产生

簇由上一节算法的分布式版本产生，当出现虚拟环段时触发算法执行。算法执行完毕时，会根据之前的约束从每个环段的节点中挑选出簇首，接着在簇中每个节点的路由表中用ch_flag进行标注。如果多个簇首同时触发簇的产生过程，则每个簇首需要根据自己的标识去发现地址空间树的信息。因此，必须在簇首之间传递地址空间树的发现数据，以便快速找出到地址空间树根节点的最短路径。

3.2 节点的加入和退出

当将传统的P2P协议思想应用到MANET(Mobile Ad Hoc Networks)中时，往往因为移动网络节点的暂不可达性、受限的资源(例如电能)或是节点移动性产生的网络振动和分割问题，实际使用时获得的性能普遍不理想。VRR协议设计了简单的双向故障检测机制，能够有效地发现上述问题并且修复路由状态，保证虚拟环始终保持一致。基于VRR，我们设计了一系列有效的机制以应对在维护簇结构时面临的网络问题。

3.2.1 节点加入

准备加入的节点u首先申请获得一个全局惟一的Kautz串标识S，之后周期地广播加入请求，寻找已经加入网络并活跃的物理邻居节点，作为加入网络并获取路由信息的代理节点。找到代理节点之后，u首先产生从代理节点到自身标识S的路由，该路由按照后根序遍历地址空间树，并最终抵达一棵子树，该子树根节点W的标识是u标识S的前缀。接着W会发起一个join信息。从节点W开始，如果当前节点有一个带有大量未分配地址段的邻居节点，则将join信息推送到该邻居节点。该推送过程会一直持续，直到join信息抵达某个节点V，节点V没有一个带有大量未分配地址段的邻居节点。接着，节点u被分配到包含节点V的簇中。接下来考虑簇的大小是否满足约束条件，此时存在四种需要考虑的情况。最简单的情况是若此时簇的大小小于2k-1，且新加入的节点u不会成为新的簇首(Clusterhead)，则只要简单地将节点u加入到簇虚拟环的适当位置即可；第二种情况，若当且仅当节点u成为新的簇首，则启动簇首替换过程；如果簇的大小大于2k-1，不论新加节点u的标识是多少，当前簇都需要被分隔成两个新簇；加入簇后，新节点u需要初始化自身的路由表，并且更新同簇邻居节点的路由表。

3.2.2 节点退出

当有节点u脱离网络，可根据自身的标识采用两种不同的机制完成。如果节点u是某个簇中的普通节点，他只需要简单地脱离网络，我们使用VRR中已有的故障检测和修复机制来维护虚拟环的一致性。如果节点u是簇首节点，则需要计算簇的新簇首，不过这个计算过程需要保证是非中断式的，因为新节点带来的路由更新信息将在簇中传播，而且所有被更新路由信息的节点地址不能被修改。

4 算法的实现

基于网络模拟器NS-2.4[17]，我们评估了设计的分簇算法性能。实验中模拟的节点规模为200，均匀分布在300×300的正方形区域上。每次模拟随机选择两个节点进行路由，然后计算100次实验数据的平均值。每次实验运行1 000 s，采样最后的500 s作为评估值，不采样之前500 s的实验数据是为了保证路由协议运行达到稳定状态。同时，我们将路由协议VRR[18]和分簇路由协议的性能进行了对比。

实验设计为：针对MP2P系统在校园网络和车载网络两种典型环境中，研究手持移动设备在不同速度模式下协议的性能。我们设计了低移动(模拟在校园网络中个人手持移动设备时的速度，比如慢跑)和高移动(车载网络时的速度)两种测试场景：低移动场景中节点的移动速度为5 m/s，高速移动场景中节点的移动速度为20 m/s。进一步，我们分别测试了在网络规模增加和载荷增加情况下协议的性能。

Figure 3 Performance with increasing number of CBR flows in high mobility图3 低速情况下载荷增加时的性能

Figure 4 Performance with increasing number of CBR flows in high mobility图4 高速情况下载荷增加时性能

在低速的情况下，一开始三种协议都能够获得较好的数据发送比率和低延迟，随着载荷的增加，数据发送比率也随之增加。图3显示，我们设计的分簇路由协议能够获得更低的延迟和更高的数据发送比率，这是因为Kautz图的特点以及簇大小约束条件能保证更好的负载平衡。高速场景下的测试情况如图4所示，从图4中也能得到和图3类似的结论。进一步比较我们设计的分簇路由协议能获得优于VRR的性能，这是因为当网络振动问题频繁出现时，分簇算法能够保证路由协议具有更好的可扩展性。

图5和图6显示了当保持载荷不变，增加节点数目对路由协议性能的影响。图5中，当节点数小于80时，我们设计的分簇路由协议能获得较高的数据发送比率和较低的延迟。随着节点数的增加，数据分发比率逐渐降低，延迟增加。相比其他两个协议，我们设计的分簇路由协议能够获得更好的数据发送比率和延迟。高速场景下，图6也显示出和图5相同的结论。

Figure 5 Performance with increasing size in low mobility图5 低速情况下节点增加时性能

Figure 6 Performance with increasing size in high mobility图6 高速情况下节点增加时性能

5 结束语

在本文中，我们根据Kautz图设计了一个有效的分簇算法：首先定义了地址空间树，接着使用Kautz结构定义节点标识，再使用后根序和宽度优先算法遍历地址空间树产生簇。实验结果表明，与VRR和MADPastry相比我们的分簇算法能够获得更低的网络延迟、更好的可扩展性和性能。当面对MP2P网络的节点移动和网络振动问题时，使用我们设计的分簇算法能够表现出更好的总体性能。

[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.