非穩態拓撲下的機會網絡分層模型

許 崗 金海和,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