非稳态拓扑下的机会网络分层模型

许 岗 金海和,2 刘 靖

(1内蒙古大学计算机学院, 呼和浩特 010021)(2内蒙古大学公共管理学院, 呼和浩特 010021)



非稳态拓扑下的机会网络分层模型

许 岗1金海和1,2刘 靖1

(1内蒙古大学计算机学院, 呼和浩特 010021)(2内蒙古大学公共管理学院, 呼和浩特 010021)

为了解决在消息敏感的机会网络中社团划分结果不可重用的问题,提出了一种与消息类型相匹配的机会网络分层模型.首先,将机会网络的物理节点集映射为与消息类型匹配的虚拟节点集,并以此为基础建立虚拟机会网络层;然后,在虚拟机会网络层上,建立虚拟节点集的社会关系;最后,对虚拟节点集的社会关系进行社团划分.实验结果表明:在消息数量相同的条件下,当消息序列中相邻位置消息的类型差异度分别为40%和100%时,在虚拟层上进行社团划分的时间与在物理机会网络上直接进行社团划分的时间相比分别减少约58%和89%;基于分层模型的社团划分的运行次数仅依赖于消息类型的数量,而不会随消息数量或消息序列中不同类型消息交错方式的变化而变化.

机会网络;敏感性;虚拟机会网络分层模型;社团划分

近年来,随着短距离移动通信终端的发展,研究者们提出了一种机会网络的新型无线移动自组网[1].在机会网络中,节点之间不存在端到端的链路,消息传输延迟大、成本低,适用于不易架设网络基础设施的环境中[2],如灾难区域的通信、野生动物信息获取和跟踪[3-4]、草原生态环境监测等.

受人影响的机会网络的社会关系中存在着社团.目前,已出现多种基于社团划分[5-8]的机会网络路由算法[2,9-11]，这些算法都是基于稳态拓扑的.然而,在机会网络中,节点具有自私性,不同类型消息传播时可用的节点和拓扑结构不同,拓扑对消息敏感而呈现非稳态,已有的社团划分算法结果无法被重复利用,故会消耗大量的处理器计算时间.

为解决社团划分结果不可重用的问题,本文提出了一种非稳态拓扑下的机会网络分层模型,将消息敏感的非稳态拓扑转化为消息敏感的稳态拓扑.仿真结果表明,利用这种分层模型可降低社团划分所消耗的时间.

1 分层模型

受人影响的机会网络不具备稳定的物理拓扑结构,但具有较为稳定的社会关系拓扑结构.除非特别说明,本文中提到的拓扑结构是指社会关系拓扑结构.

1.1 虚拟机会网络层

不同类型的消息在机会网络中传播时,可用节点集和社会关系拓扑结构不同,导致社团划分结果不可重用.为了将消息敏感的非稳态社会关系拓扑转化为消息敏感的稳态社会关系拓扑,提出了与物理机会网络相对应的虚拟机会网络分层映射模型.

定义1 消息是指机会网络中传播的数据.为每个消息增加1个头,这个头用于表示消息的类型.

定义2 虚拟移动节点V是指机会网络中物理移动节点N的映射.当编号为i的物理移动节点Ni可传递第K种类型的消息MK时,称虚拟移动节点VKi为可传递消息MK的物理移动节点Ni的映射.

定义4 由虚拟移动节点集IK构成的机会网络被称为消息MK的虚拟机会网络层HK.它是物理节点集J构成的物理机会网络在消息MK下的映射.

图1为机会网络NET的社会关系拓扑结构,由16个节点和节点间社会关系构成.图中,能传递消息MⅠ的节点集为{1,2,3,4,5,7,11,12,13,14,15};能传递消息MⅡ的节点集为{2,3,4,5,7,8,15,16};能传递消息MⅢ的节点集为{1,4,5,6,8,9,11,12,14,15}.

图1 机会网络NET的社会关系拓扑结构

针对不同类型的消息,可将物理机会网络映射为与消息类型相匹配的虚拟机会网络层(见图2).对某一种类型的消息而言,与其匹配的虚拟层上的节点集和社会关系拓扑结构是稳定的.虚拟机会网络层的节点集是机会网络中物理节点集的真子集.

(a) MⅠ

(b) MⅡ

(c) MⅢ

1.2 虚拟路径

定义5 消息转发时顺序经过的虚拟节点序列号被称为消息传递的虚拟路径.

设消息MⅢ在虚拟机会网络层上传播,可用节点集为{1,4,5,6,8,9,11,12,14,15},拓扑结构如图2(c)所示.现有消息MⅢ从源节点1产生,需要传递到目的节点11.选择消息对应的虚拟机会网络层,并在虚拟机会网络层上进行路径规划,便可得到如图3所示的虚拟路径.

2 分层模型构建算法

对某一种类型的消息而言,建立与消息类型匹

图3 消息MⅢ传播的虚拟路径

配的虚拟机会网络层,虚拟层上的节点集和社会关系拓扑结构是稳定的.

为了建立虚拟机会网络层,提出了一种分层模型构建算法.首先,将物理节点集映射为虚拟节点集;然后,将机会网络的社会关系拓扑图映射为虚拟层上的社会关系拓扑图.

2.1 分层映射模型

建立分层映射模型的重点是区分移动节点对不同类型消息的敏感性,即将对同一类型消息敏感的移动节点划分在同一层.机会网络中,在特定场景下,所有节点都已获得网络中消息的类型;在非特定场景下,节点则未获得网络中消息的类型.

2.1.1 特定场景

在特定应用场景下,机会网络中的节点能够获知网络中传播的消息的类型.例如,在用于草场监测的移动传感器网络中,所有节点和消息都是定制的,故节点已获知所有传播消息的类型.算法1给出了特定场景下建立的分层映射模型伪代码.

算法1 特定场景下的分层映射模型

输入:物理移动节点集J.

输出:虚拟机会网络层HK.

Hierarchical_Model_All_Type()

{ENQUEUE(Q1,J) //将J中的节点依次放入队列Q1中

WhileQ1.h!=NULL //Q1队列头元素不为空

DEQUEUE(Q1,Ni++) //取Q1队列头元素放入Ni中

WhileNi.Message_Memory_STACK!=NULL

//扫描Ni消息存储区的所有消息

If Pop(Ni.Message_Memory_STACK==MK)

//如果Ni可以传递消息MK

Ni->VKi,add(HK,VKi) //在HK上为Ni建立VKi

End While

End While

}

2.1.2 非特定场景

在非特定场景下,机会网络中的节点无法提前获知网络中传播消息的类型.算法2给出了非特定场景下建立的分层映射模型伪代码.

算法2 非特定场景下的分层映射模型

输入:物理移动节点集J,测试消息集S.

输出:虚拟机会网络层HK.

Hierarchical_Model_Part_Type()

{ENQUEUE(Q2,S) //将S中的消息依次放入队列Q2中

WhileQ2.h!=NULL //Q2队列头元素不为空

DEQUEUE(Q2,MK) //取Q2队列头元素放入MK中

ENQUEUE(Q1,J) //将J中的节点依次放入队列Q1

WhileQ1.h!=NULL //Q1队列头元素不为空

DEQUEUE(Q1,Ni++) //取Q1队列头元素放入Ni中

SendMKtoNi//将消息MK发送至Ni

If Pop(Ni.Message_Memory_STACK==MK)

//如果Ni可以传递消息MK

Ni->VKi,add(HK,VKi) //在HK上为Ni建立VKi

End While

End While

}

在非特定场景下,节点没有提前获知消息的类型,故需要对每个节点能够处理的消息类型进行测试.算法2为每个类型的消息建立了虚拟机会网络层.

利用算法1和算法2为消息MⅣ,MⅤ,MⅥ建立虚拟机会网络层A,为消息MⅦ,MⅧ,MⅨ建立虚拟机会网络层B(见图4).在机会网络NET中,节点集{2,4,5,6,7,8,9,11,12,14,15}可转发消息MⅣ,MⅤ,MⅥ,节点集{1,2,3,5,10,11,13,15}可转发消息MⅦ,MⅧ,MⅨ.假设在机会网络中传播的消息序列为MⅦ→MⅣ→MⅧ→MⅤ→MⅨ→MⅥ.由于相邻消息类型各不相同,故每传播一条消息时,可见的节点集和拓扑结构也各不相同,已有的社团划分结果不能被重复利用,需进行6次社团划分.将机会网络NET映射为与消息类型匹配的虚拟机会网络层A和B,社团划分只需在虚拟机会网络层上进行.消息MⅣ,MⅤ,MⅥ以虚拟层A的社团划分结果为依据进行路由规划,消息MⅦ,MⅧ,MⅨ以虚拟层B的社团划分结果为依据进行路由规划.此时,社团划分的运行次数并不随消息数量或消息序列中不同消息类型交错方式的变化而变化,仅与消息类型的数量相关.

(a) 虚拟机会网络层A

(b) 虚拟机会网络层B

2.2 虚拟层上的拓扑模型

在受人影响的机会网络中,节点的移动和相遇具有社会属性.从一个足够长的时间段(大于等于48 h)来分析,节点之间的社会关系是稳定的.

根据机会网络的特征,在虚拟机会网络层上建立如下的社会关系拓扑图模型伪代码.

算法3 社会关系拓扑图模型

输入:IK.

输出:HK上的社会关系拓扑图模型.

Map_to_graph()

{

Set(min_rtime, min_mdis, min_mtime, min_mcont)

While run_time>min_rtime //网络运行时长超过给定阈值

Whilei:1->n;j:1->n

If Dis(VKi,VKj)<=min_mdis //节点相遇

If Stay_T(VKi,VKj)>min_mtime //相遇有效

num_contij++; //统计有效相遇次数

End If

End If

If num_contij>min_mcont //相遇次数满足阈值

Connect(VKi,VKj); //连接VKi和VKj

End If

End While

End While

}

算法1和算法2是将移动节点映射为虚拟节点,算法3则是在算法1或算法2形成的虚拟节点集上建立稳态的社会关系拓扑图模型.例如,利用算法1或算法2可得到图4中虚拟机会网络层上的节点,利用算法3则可建立其社会关系拓扑结构.

3 实验结果及分析

3.1 时间复杂度

目前,学者们已提出多种社团划分算法,如Kernighan_Lin算法[5]、GN算法[6]、Newman快速算法[7]和派系过滤算法[8]等;这些算法的时间复杂度都大于线性时间量级.以时间复杂度较小的Newman快速算法为例,其时间复杂度为O((m+n)n),其中m为边数.

下面以Newman快速算法为例,证明分层模型的有效性.假设网络为稀疏网络,给定机会网络NET.根据处理器是否具备并行处理能力的特点,对时间复杂度进行分析.

1) 无并行处理情况

设6种不同类型的消息U,R,F,X,Y,Z,每个类型包含c个消息,消息以组的形式在机会网络中传播,每组消息都以U→X→R→Y→F→Z的顺序交错传播.根据2.1节中的算法建立6层虚拟机会网络层,其时间复杂度为6O(n).虚拟机会网络层上运行社团划分的时间复杂度为6O(n2).应用分层模型后,社团划分总的时间复杂度为6(O(n2)+O(n)).

如果直接在机会网络上进行消息传播,要进行6c次社团划分,时间复杂度为6cO(n2).随着机会网络的运行,网络中传递的消息数量逐步增加.c随时间不断增大,不妨设c>n,分层模型下社团划分时间复杂度仍为6(O(n2)+O(n)),而直接在机会网络上进行社团划分的时间复杂度为6O(n3).显然,当n足够大(如n=30)时,6O(n3)≫6(O(n2)+O(n)).将消息类型数推广为整数w,且w∈[1,10],有wO(n3)≫w(O(n2)+O(n)).

2) 有并行处理情况

设处理器数为b,消息类型数为w(w∈[1,10]),建立w个虚拟机会网络层,将w个虚拟层分解为w/b个组,每个处理器对1组虚拟层进行社团划分,则时间代价为w/b(O(n2)+O(n));而直接在机会网络上进行社团划分的时间复杂度与消息数及消息序列类型交错方式相关,仍为wO(n3),即wO(n3)≫w/b(O(n2)+O(n))成立.

由此可知,当c和n足够大 (如n=30,c=50) 时,使用分层模型进行社团划分的计算代价较小,且社团划分结果可重用.

3.2 空间复杂度

在机会网络中,由于消息种类(如音频和文本、及时性消息和非及时性消息等)数量不大于10,故需要的空间代价较少,4个二进制位即可解决.由此可知,分层模型几乎没有增加空间复杂度,且对于消息种类的增加具有良好的扩展性.

3.3 实验结果分析

算法使用C语言实现,并在计算机上进行了多组仿真实验.实验使用的计算机硬件配置如下:处理器为Inter(R) Core(TM) i5-2410M 2.3 GHz CPU,内存为4 GB,操作系统为Windows 7旗舰版.

仿真机会网络运行48 h后,节点形成较为稳定的社会拓扑关系(见图5).该网络节点数为64,边数为901.设置部分节点对消息敏感.利用极大团算法进行社团划分.

在如图5所示的机会网络社会关系拓扑中,假设传播的消息类型共计10种,每种消息类型中包含20个消息实例.机会网络中有64个节点,设置节点1～节点30对消息敏感,其他34个节点则可以转发任意种类的消息.节点1～节点3不转发类型1的消息,节点4～节点6不转发类型2的消息,以此类推,节点28～节点30不转发类型10的消息.这些消息以消息序列的形式发送,共计20组消息序列;在每组消息序列中,每种类型的消息各1个.如图6所示,当消息序列中相邻消息的类型差异度q=40%时,基于分层模型的社团划分时间较基于物理机会网络的社团划分时间减少约58%;当q=100%时,前者较后者减少约89%.由此可知,建立虚拟机会网络层后,社团划分次数只依赖于消息类型数,而与消息数或消息序列交错方式无关,且由于社团划分结果可重用,极大减少了社团划分次数,节约了社团划分时间.

图5 机会网络的社会关系拓扑图

图6 社团划分时间对比

4 结语

为了解决社团划分结果不可重用的问题,提出并形式化定义了虚拟机会网络分层模型,应用该模型将消息敏感的非稳态拓扑转化为消息敏感的稳态拓扑.虚拟机会网络层解除了社团划分次数与消息数及消息序列交错方式的相关性,使社团划分次数不会随着消息数量以及消息序列交错方式的改变而变化.实验结果表明,采用虚拟机会网络分层模型可有效解决消息敏感的机会网络中社团划分结果不可重用的问题,极大减少了社团划分运行的次数,节约了机会网络中消息传递的时间.

References)

[1]熊永平,孙利民,牛建伟,等. 机会网络[J]. 软件学报, 2009, 20(1): 124-137. Xiong Yongping, Sun Limin, Niu Jianwei, et al. Opportunistic networks[J].JournalofSoftware, 2009, 20(1): 124-137. (in Chinese)

[2]牛建伟,周兴,刘燕,等. 一种基于社区机会网络的消息传输算法[J]. 计算机研究与发展, 2009, 46(12): 2068-2075. Niu Jianwei, Zhou Xing, Liu Yan, et al. A message transmission scheme for community-based opportunistic network[J].JournalofComputerResearchandDevelopment, 2009, 46(12): 2068-2075. (in Chinese)

[3]Juang P, Oki H, Wang Y, et al. Energy-efficient computing for wildlife tracking:design tradeoffs and early experiences with ZebraNet [J].ACMSIGPLANNotices, 2002, 37(10): 96-107.

[4]Small T, Haas Z J. The shared wireless infostation model: a new ad hoc networking paradigm(or where there is a whale, there is a way) [C]//Proceedingsofthe4thACMInternationalSymposiumonMobileAdHocNetworking&Computing. New York, USA, 2003: 233-244.

[5]Kernighan B W,Lin S. An efficient heuristic procedure for partitioning graphs [J].BellSystemTechnicalJournal, 1970, 49(2): 291-307.

[6]Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society [J].Nature, 2005, 435(7043): 814-818.

[7]Girvan M,Newman M E J. Community structure in social and biological networks [J].ProceedingsoftheNationalAcademyofSciences, 2002, 99(12): 7821-7826.

[8]Newman M E J. Fast algorithm for detecting community structure in networks [J].PhysicalReviewE, 2004, 69(6): 066133-1-066133-5.

[9]Hui P, Crowcroft J, Yoneki E. Bubble rap: social-based forwarding in delay-tolerant networks [J].IEEETransactionsonMobileComputing, 2011, 10(11): 1576-1589.

[10]彭舰, 李梦诗, 刘唐, 等. 机会网络中基于节点社会性的数据转发策略[J]. 四川大学学报：工程科学版, 2013, 45(5): 57-63. Peng Jian, Li Mengshi, Liu Tang, et al. Nodal sociality-based data forwarding for opportunistic networks[J].JournalofSichuanUniversity:EngineeringScienceEdition, 2013, 45(5): 57-63. (in Chinese)

[11]Qin Jun, Zhu Hongzi, Zhu Yanmin, et al. POST: exploiting dynamic sociality for mobile advertising in vehicular networks [C]//Proceedingsof2014IEEEConferenceonComputerCommunications. Toronto, Canada, 2014: 1761-1769.

Opportunistic network hierarchical model in unsteady topology

Xu Gang1Jin Haihe1,2Liu Jing1

(1College of Computer Science, Inner Mongolia University, Huhhot 010021, China) (2College of Public Management, Inner Mongolia University, Huhhot 010021, China)

In order to solve the problem that the community detection results cannot be repeatedly used in the information sensitivity opportunistic network, an opportunistic network hierarchical model which matches with information types is proposed. First, the physical node set in the opportunistic network is mapped as a virtual node set which matches with information types, based on which the virtual opportunistic network layer is established. Then, the social relationship of the virtual node set is built on the virtual opportunistic network layer. Finally, community detection is conducted on the social relationship of the virtual node set. The experimental results show that when the difference degrees of the types of adjacent information in the information sequence are 40% and 100%, the time consumption in community detection on the virtual layer decreases by about 58% and 89% compared with that in the physical opportunistic network with the same information quantity, respectively. The execution number of the community detection operations based on the layer model only depends on the number of the information types, and does not change with the change of the information quantity or the overlapping ways of the different information types in the information sequence.

opportunistic network; sensitivity; virtual opportunistic network hierarchical model; community detection

10.3969/j.issn.1001-0505.2015.03.005

2014-10-31. 作者简介: 许岗(1980—)，男，博士生，讲师；金海和(联系人)，男，博士，教授，博士生导师, jin_haihe@126.com.

内蒙古自治区自然科学基金资助项目(2013MS0904).

许岗,金海和,刘靖.非稳态拓扑下的机会网络分层模型[J].东南大学学报:自然科学版,2015,45(3):438-442.

10.3969/j.issn.1001-0505.2015.03.005

TP393

A

1001-0505(2015)03-0438-05