許 崗 金海和,2 劉 靖

(1內(nèi)蒙古大學(xué)計算機(jī)學(xué)院, 呼和浩特 010021)(2內(nèi)蒙古大學(xué)公共管理學(xué)院, 呼和浩特 010021)

?

非穩(wěn)態(tài)拓?fù)湎碌臋C(jī)會網(wǎng)絡(luò)分層模型

許 崗1金海和1,2劉 靖1

(1內(nèi)蒙古大學(xué)計算機(jī)學(xué)院, 呼和浩特 010021)(2內(nèi)蒙古大學(xué)公共管理學(xué)院, 呼和浩特 010021)

為了解決在消息敏感的機(jī)會網(wǎng)絡(luò)中社團(tuán)劃分結(jié)果不可重用的問題,提出了一種與消息類型相匹配的機(jī)會網(wǎng)絡(luò)分層模型.首先,將機(jī)會網(wǎng)絡(luò)的物理節(jié)點集映射為與消息類型匹配的虛擬節(jié)點集,并以此為基礎(chǔ)建立虛擬機(jī)會網(wǎng)絡(luò)層;然后,在虛擬機(jī)會網(wǎng)絡(luò)層上,建立虛擬節(jié)點集的社會關(guān)系;最后,對虛擬節(jié)點集的社會關(guān)系進(jìn)行社團(tuán)劃分.實驗結(jié)果表明:在消息數(shù)量相同的條件下,當(dāng)消息序列中相鄰位置消息的類型差異度分別為40%和100%時,在虛擬層上進(jìn)行社團(tuán)劃分的時間與在物理機(jī)會網(wǎng)絡(luò)上直接進(jìn)行社團(tuán)劃分的時間相比分別減少約58%和89%;基于分層模型的社團(tuán)劃分的運行次數(shù)僅依賴于消息類型的數(shù)量,而不會隨消息數(shù)量或消息序列中不同類型消息交錯方式的變化而變化.

機(jī)會網(wǎng)絡(luò);敏感性;虛擬機(jī)會網(wǎng)絡(luò)分層模型;社團(tuán)劃分

近年來,隨著短距離移動通信終端的發(fā)展,研究者們提出了一種機(jī)會網(wǎng)絡(luò)的新型無線移動自組網(wǎng)[1].在機(jī)會網(wǎng)絡(luò)中,節(jié)點之間不存在端到端的鏈路,消息傳輸延遲大、成本低,適用于不易架設(shè)網(wǎng)絡(luò)基礎(chǔ)設(shè)施的環(huán)境中[2],如災(zāi)難區(qū)域的通信、野生動物信息獲取和跟蹤[3-4]、草原生態(tài)環(huán)境監(jiān)測等.

受人影響的機(jī)會網(wǎng)絡(luò)的社會關(guān)系中存在著社團(tuán).目前,已出現(xiàn)多種基于社團(tuán)劃分[5-8]的機(jī)會網(wǎng)絡(luò)路由算法[2,9-11]，這些算法都是基于穩(wěn)態(tài)拓?fù)涞?然而,在機(jī)會網(wǎng)絡(luò)中,節(jié)點具有自私性,不同類型消息傳播時可用的節(jié)點和拓?fù)浣Y(jié)構(gòu)不同,拓?fù)鋵ο⒚舾卸尸F(xiàn)非穩(wěn)態(tài),已有的社團(tuán)劃分算法結(jié)果無法被重復(fù)利用,故會消耗大量的處理器計算時間.

為解決社團(tuán)劃分結(jié)果不可重用的問題,本文提出了一種非穩(wěn)態(tài)拓?fù)湎碌臋C(jī)會網(wǎng)絡(luò)分層模型,將消息敏感的非穩(wěn)態(tài)拓?fù)滢D(zhuǎn)化為消息敏感的穩(wěn)態(tài)拓?fù)?仿真結(jié)果表明,利用這種分層模型可降低社團(tuán)劃分所消耗的時間.

1 分層模型

受人影響的機(jī)會網(wǎng)絡(luò)不具備穩(wěn)定的物理拓?fù)浣Y(jié)構(gòu),但具有較為穩(wěn)定的社會關(guān)系拓?fù)浣Y(jié)構(gòu).除非特別說明,本文中提到的拓?fù)浣Y(jié)構(gòu)是指社會關(guān)系拓?fù)浣Y(jié)構(gòu).

1.1 虛擬機(jī)會網(wǎng)絡(luò)層

不同類型的消息在機(jī)會網(wǎng)絡(luò)中傳播時,可用節(jié)點集和社會關(guān)系拓?fù)浣Y(jié)構(gòu)不同,導(dǎo)致社團(tuán)劃分結(jié)果不可重用.為了將消息敏感的非穩(wěn)態(tài)社會關(guān)系拓?fù)滢D(zhuǎn)化為消息敏感的穩(wěn)態(tài)社會關(guān)系拓?fù)?提出了與物理機(jī)會網(wǎng)絡(luò)相對應(yīng)的虛擬機(jī)會網(wǎng)絡(luò)分層映射模型.

定義1 消息是指機(jī)會網(wǎng)絡(luò)中傳播的數(shù)據(jù).為每個消息增加1個頭,這個頭用于表示消息的類型.

定義2 虛擬移動節(jié)點V是指機(jī)會網(wǎng)絡(luò)中物理移動節(jié)點N的映射.當(dāng)編號為i的物理移動節(jié)點Ni可傳遞第K種類型的消息MK時,稱虛擬移動節(jié)點VKi為可傳遞消息MK的物理移動節(jié)點Ni的映射.

定義4 由虛擬移動節(jié)點集IK構(gòu)成的機(jī)會網(wǎng)絡(luò)被稱為消息MK的虛擬機(jī)會網(wǎng)絡(luò)層HK.它是物理節(jié)點集J構(gòu)成的物理機(jī)會網(wǎng)絡(luò)在消息MK下的映射.

圖1為機(jī)會網(wǎng)絡(luò)NET的社會關(guān)系拓?fù)浣Y(jié)構(gòu),由16個節(jié)點和節(jié)點間社會關(guān)系構(gòu)成.圖中,能傳遞消息MⅠ的節(jié)點集為{1,2,3,4,5,7,11,12,13,14,15};能傳遞消息MⅡ的節(jié)點集為{2,3,4,5,7,8,15,16};能傳遞消息MⅢ的節(jié)點集為{1,4,5,6,8,9,11,12,14,15}.

圖1 機(jī)會網(wǎng)絡(luò)NET的社會關(guān)系拓?fù)浣Y(jié)構(gòu)

針對不同類型的消息,可將物理機(jī)會網(wǎng)絡(luò)映射為與消息類型相匹配的虛擬機(jī)會網(wǎng)絡(luò)層(見圖2).對某一種類型的消息而言,與其匹配的虛擬層上的節(jié)點集和社會關(guān)系拓?fù)浣Y(jié)構(gòu)是穩(wěn)定的.虛擬機(jī)會網(wǎng)絡(luò)層的節(jié)點集是機(jī)會網(wǎng)絡(luò)中物理節(jié)點集的真子集.

(a) MⅠ

(b) MⅡ

(c) MⅢ

1.2 虛擬路徑

定義5 消息轉(zhuǎn)發(fā)時順序經(jīng)過的虛擬節(jié)點序列號被稱為消息傳遞的虛擬路徑.

設(shè)消息MⅢ在虛擬機(jī)會網(wǎng)絡(luò)層上傳播,可用節(jié)點集為{1,4,5,6,8,9,11,12,14,15},拓?fù)浣Y(jié)構(gòu)如圖2(c)所示.現(xiàn)有消息MⅢ從源節(jié)點1產(chǎn)生,需要傳遞到目的節(jié)點11.選擇消息對應(yīng)的虛擬機(jī)會網(wǎng)絡(luò)層,并在虛擬機(jī)會網(wǎng)絡(luò)層上進(jìn)行路徑規(guī)劃,便可得到如圖3所示的虛擬路徑.

2 分層模型構(gòu)建算法

對某一種類型的消息而言,建立與消息類型匹

圖3 消息MⅢ傳播的虛擬路徑

配的虛擬機(jī)會網(wǎng)絡(luò)層,虛擬層上的節(jié)點集和社會關(guān)系拓?fù)浣Y(jié)構(gòu)是穩(wěn)定的.

為了建立虛擬機(jī)會網(wǎng)絡(luò)層,提出了一種分層模型構(gòu)建算法.首先,將物理節(jié)點集映射為虛擬節(jié)點集;然后,將機(jī)會網(wǎng)絡(luò)的社會關(guān)系拓?fù)鋱D映射為虛擬層上的社會關(guān)系拓?fù)鋱D.

2.1 分層映射模型

建立分層映射模型的重點是區(qū)分移動節(jié)點對不同類型消息的敏感性,即將對同一類型消息敏感的移動節(jié)點劃分在同一層.機(jī)會網(wǎng)絡(luò)中,在特定場景下,所有節(jié)點都已獲得網(wǎng)絡(luò)中消息的類型;在非特定場景下,節(jié)點則未獲得網(wǎng)絡(luò)中消息的類型.

2.1.1 特定場景

在特定應(yīng)用場景下,機(jī)會網(wǎng)絡(luò)中的節(jié)點能夠獲知網(wǎng)絡(luò)中傳播的消息的類型.例如,在用于草場監(jiān)測的移動傳感器網(wǎng)絡(luò)中,所有節(jié)點和消息都是定制的,故節(jié)點已獲知所有傳播消息的類型.算法1給出了特定場景下建立的分層映射模型偽代碼.

算法1 特定場景下的分層映射模型

輸入:物理移動節(jié)點集J.

輸出:虛擬機(jī)會網(wǎng)絡(luò)層HK.

Hierarchical_Model_All_Type()

{ENQUEUE(Q1,J) //將J中的節(jié)點依次放入隊列Q1中

WhileQ1.h!=NULL //Q1隊列頭元素不為空

DEQUEUE(Q1,Ni++) //取Q1隊列頭元素放入Ni中

WhileNi.Message_Memory_STACK!=NULL

//掃描Ni消息存儲區(qū)的所有消息

If Pop(Ni.Message_Memory_STACK==MK)

//如果Ni可以傳遞消息MK

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

End While

End While

}

2.1.2 非特定場景

在非特定場景下,機(jī)會網(wǎng)絡(luò)中的節(jié)點無法提前獲知網(wǎng)絡(luò)中傳播消息的類型.算法2給出了非特定場景下建立的分層映射模型偽代碼.

算法2 非特定場景下的分層映射模型

輸入:物理移動節(jié)點集J,測試消息集S.

輸出:虛擬機(jī)會網(wǎng)絡(luò)層HK.

Hierarchical_Model_Part_Type()

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

WhileQ2.h!=NULL //Q2隊列頭元素不為空

DEQUEUE(Q2,MK) //取Q2隊列頭元素放入MK中

ENQUEUE(Q1,J) //將J中的節(jié)點依次放入隊列Q1

WhileQ1.h!=NULL //Q1隊列頭元素不為空

DEQUEUE(Q1,Ni++) //取Q1隊列頭元素放入Ni中

SendMKtoNi//將消息MK發(fā)送至Ni

If Pop(Ni.Message_Memory_STACK==MK)

//如果Ni可以傳遞消息MK

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

End While

End While

}

在非特定場景下,節(jié)點沒有提前獲知消息的類型,故需要對每個節(jié)點能夠處理的消息類型進(jìn)行測試.算法2為每個類型的消息建立了虛擬機(jī)會網(wǎng)絡(luò)層.

利用算法1和算法2為消息MⅣ,MⅤ,MⅥ建立虛擬機(jī)會網(wǎng)絡(luò)層A,為消息MⅦ,MⅧ,MⅨ建立虛擬機(jī)會網(wǎng)絡(luò)層B(見圖4).在機(jī)會網(wǎng)絡(luò)NET中,節(jié)點集{2,4,5,6,7,8,9,11,12,14,15}可轉(zhuǎn)發(fā)消息MⅣ,MⅤ,MⅥ,節(jié)點集{1,2,3,5,10,11,13,15}可轉(zhuǎn)發(fā)消息MⅦ,MⅧ,MⅨ.假設(shè)在機(jī)會網(wǎng)絡(luò)中傳播的消息序列為MⅦ→MⅣ→MⅧ→MⅤ→MⅨ→MⅥ.由于相鄰消息類型各不相同,故每傳播一條消息時,可見的節(jié)點集和拓?fù)浣Y(jié)構(gòu)也各不相同,已有的社團(tuán)劃分結(jié)果不能被重復(fù)利用,需進(jìn)行6次社團(tuán)劃分.將機(jī)會網(wǎng)絡(luò)NET映射為與消息類型匹配的虛擬機(jī)會網(wǎng)絡(luò)層A和B,社團(tuán)劃分只需在虛擬機(jī)會網(wǎng)絡(luò)層上進(jìn)行.消息MⅣ,MⅤ,MⅥ以虛擬層A的社團(tuán)劃分結(jié)果為依據(jù)進(jìn)行路由規(guī)劃,消息MⅦ,MⅧ,MⅨ以虛擬層B的社團(tuán)劃分結(jié)果為依據(jù)進(jìn)行路由規(guī)劃.此時,社團(tuán)劃分的運行次數(shù)并不隨消息數(shù)量或消息序列中不同消息類型交錯方式的變化而變化,僅與消息類型的數(shù)量相關(guān).

(a) 虛擬機(jī)會網(wǎng)絡(luò)層A

(b) 虛擬機(jī)會網(wǎng)絡(luò)層B

2.2 虛擬層上的拓?fù)淠Ｐ?/p>

在受人影響的機(jī)會網(wǎng)絡(luò)中,節(jié)點的移動和相遇具有社會屬性.從一個足夠長的時間段(大于等于48 h)來分析,節(jié)點之間的社會關(guān)系是穩(wěn)定的.

根據(jù)機(jī)會網(wǎng)絡(luò)的特征,在虛擬機(jī)會網(wǎng)絡(luò)層上建立如下的社會關(guān)系拓?fù)鋱D模型偽代碼.

算法3 社會關(guān)系拓?fù)鋱D模型

輸入:IK.

輸出:HK上的社會關(guān)系拓?fù)鋱D模型.

Map_to_graph()

{

Set(min_rtime, min_mdis, min_mtime, min_mcont)

While run_time>min_rtime //網(wǎng)絡(luò)運行時長超過給定閾值

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

If Dis(VKi,VKj)<=min_mdis //節(jié)點相遇

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

num_contij++; //統(tǒng)計有效相遇次數(shù)

End If

End If

If num_contij>min_mcont //相遇次數(shù)滿足閾值

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

End If

End While

End While

}

算法1和算法2是將移動節(jié)點映射為虛擬節(jié)點,算法3則是在算法1或算法2形成的虛擬節(jié)點集上建立穩(wěn)態(tài)的社會關(guān)系拓?fù)鋱D模型.例如,利用算法1或算法2可得到圖4中虛擬機(jī)會網(wǎng)絡(luò)層上的節(jié)點,利用算法3則可建立其社會關(guān)系拓?fù)浣Y(jié)構(gòu).

3 實驗結(jié)果及分析

3.1 時間復(fù)雜度

目前,學(xué)者們已提出多種社團(tuán)劃分算法,如Kernighan_Lin算法[5]、GN算法[6]、Newman快速算法[7]和派系過濾算法[8]等;這些算法的時間復(fù)雜度都大于線性時間量級.以時間復(fù)雜度較小的Newman快速算法為例,其時間復(fù)雜度為O((m+n)n),其中m為邊數(shù).

下面以Newman快速算法為例,證明分層模型的有效性.假設(shè)網(wǎng)絡(luò)為稀疏網(wǎng)絡(luò),給定機(jī)會網(wǎng)絡(luò)NET.根據(jù)處理器是否具備并行處理能力的特點,對時間復(fù)雜度進(jìn)行分析.

1) 無并行處理情況

設(shè)6種不同類型的消息U,R,F,X,Y,Z,每個類型包含c個消息,消息以組的形式在機(jī)會網(wǎng)絡(luò)中傳播,每組消息都以U→X→R→Y→F→Z的順序交錯傳播.根據(jù)2.1節(jié)中的算法建立6層虛擬機(jī)會網(wǎng)絡(luò)層,其時間復(fù)雜度為6O(n).虛擬機(jī)會網(wǎng)絡(luò)層上運行社團(tuán)劃分的時間復(fù)雜度為6O(n2).應(yīng)用分層模型后,社團(tuán)劃分總的時間復(fù)雜度為6(O(n2)+O(n)).

如果直接在機(jī)會網(wǎng)絡(luò)上進(jìn)行消息傳播,要進(jìn)行6c次社團(tuán)劃分,時間復(fù)雜度為6cO(n2).隨著機(jī)會網(wǎng)絡(luò)的運行,網(wǎng)絡(luò)中傳遞的消息數(shù)量逐步增加.c隨時間不斷增大,不妨設(shè)c>n,分層模型下社團(tuán)劃分時間復(fù)雜度仍為6(O(n2)+O(n)),而直接在機(jī)會網(wǎng)絡(luò)上進(jìn)行社團(tuán)劃分的時間復(fù)雜度為6O(n3).顯然,當(dāng)n足夠大(如n=30)時,6O(n3)?6(O(n2)+O(n)).將消息類型數(shù)推廣為整數(shù)w,且w∈[1,10],有wO(n3)?w(O(n2)+O(n)).

2) 有并行處理情況

設(shè)處理器數(shù)為b,消息類型數(shù)為w(w∈[1,10]),建立w個虛擬機(jī)會網(wǎng)絡(luò)層,將w個虛擬層分解為w/b個組,每個處理器對1組虛擬層進(jìn)行社團(tuán)劃分,則時間代價為w/b(O(n2)+O(n));而直接在機(jī)會網(wǎng)絡(luò)上進(jìn)行社團(tuán)劃分的時間復(fù)雜度與消息數(shù)及消息序列類型交錯方式相關(guān),仍為wO(n3),即wO(n3)?w/b(O(n2)+O(n))成立.

由此可知,當(dāng)c和n足夠大 (如n=30,c=50) 時,使用分層模型進(jìn)行社團(tuán)劃分的計算代價較小,且社團(tuán)劃分結(jié)果可重用.

3.2 空間復(fù)雜度

在機(jī)會網(wǎng)絡(luò)中,由于消息種類(如音頻和文本、及時性消息和非及時性消息等)數(shù)量不大于10,故需要的空間代價較少,4個二進(jìn)制位即可解決.由此可知,分層模型幾乎沒有增加空間復(fù)雜度,且對于消息種類的增加具有良好的擴(kuò)展性.

3.3 實驗結(jié)果分析

算法使用C語言實現(xiàn),并在計算機(jī)上進(jìn)行了多組仿真實驗.實驗使用的計算機(jī)硬件配置如下:處理器為Inter(R) Core(TM) i5-2410M 2.3 GHz CPU,內(nèi)存為4 GB,操作系統(tǒng)為Windows 7旗艦版.

仿真機(jī)會網(wǎng)絡(luò)運行48 h后,節(jié)點形成較為穩(wěn)定的社會拓?fù)潢P(guān)系(見圖5).該網(wǎng)絡(luò)節(jié)點數(shù)為64,邊數(shù)為901.設(shè)置部分節(jié)點對消息敏感.利用極大團(tuán)算法進(jìn)行社團(tuán)劃分.

在如圖5所示的機(jī)會網(wǎng)絡(luò)社會關(guān)系拓?fù)渲?假設(shè)傳播的消息類型共計10種,每種消息類型中包含20個消息實例.機(jī)會網(wǎng)絡(luò)中有64個節(jié)點,設(shè)置節(jié)點1～節(jié)點30對消息敏感,其他34個節(jié)點則可以轉(zhuǎn)發(fā)任意種類的消息.節(jié)點1～節(jié)點3不轉(zhuǎn)發(fā)類型1的消息,節(jié)點4～節(jié)點6不轉(zhuǎn)發(fā)類型2的消息,以此類推,節(jié)點28～節(jié)點30不轉(zhuǎn)發(fā)類型10的消息.這些消息以消息序列的形式發(fā)送,共計20組消息序列;在每組消息序列中,每種類型的消息各1個.如圖6所示,當(dāng)消息序列中相鄰消息的類型差異度q=40%時,基于分層模型的社團(tuán)劃分時間較基于物理機(jī)會網(wǎng)絡(luò)的社團(tuán)劃分時間減少約58%;當(dāng)q=100%時,前者較后者減少約89%.由此可知,建立虛擬機(jī)會網(wǎng)絡(luò)層后,社團(tuán)劃分次數(shù)只依賴于消息類型數(shù),而與消息數(shù)或消息序列交錯方式無關(guān),且由于社團(tuán)劃分結(jié)果可重用,極大減少了社團(tuán)劃分次數(shù),節(jié)約了社團(tuán)劃分時間.

圖5 機(jī)會網(wǎng)絡(luò)的社會關(guān)系拓?fù)鋱D

圖6 社團(tuán)劃分時間對比

4 結(jié)語

為了解決社團(tuán)劃分結(jié)果不可重用的問題,提出并形式化定義了虛擬機(jī)會網(wǎng)絡(luò)分層模型,應(yīng)用該模型將消息敏感的非穩(wěn)態(tài)拓?fù)滢D(zhuǎn)化為消息敏感的穩(wěn)態(tài)拓?fù)?虛擬機(jī)會網(wǎng)絡(luò)層解除了社團(tuán)劃分次數(shù)與消息數(shù)及消息序列交錯方式的相關(guān)性,使社團(tuán)劃分次數(shù)不會隨著消息數(shù)量以及消息序列交錯方式的改變而變化.實驗結(jié)果表明,采用虛擬機(jī)會網(wǎng)絡(luò)分層模型可有效解決消息敏感的機(jī)會網(wǎng)絡(luò)中社團(tuán)劃分結(jié)果不可重用的問題,極大減少了社團(tuán)劃分運行的次數(shù),節(jié)約了機(jī)會網(wǎng)絡(luò)中消息傳遞的時間.

References)

[1]熊永平,孫利民,牛建偉,等. 機(jī)會網(wǎng)絡(luò)[J]. 軟件學(xué)報, 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]牛建偉,周興,劉燕,等. 一種基于社區(qū)機(jī)會網(wǎng)絡(luò)的消息傳輸算法[J]. 計算機(jī)研究與發(fā)展, 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ī)會網(wǎng)絡(luò)中基于節(jié)點社會性的數(shù)據(jù)轉(zhuǎn)發(fā)策略[J]. 四川大學(xué)學(xué)報：工程科學(xué)版, 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—)，男，博士生，講師；金海和(聯(lián)系人)，男，博士，教授，博士生導(dǎo)師, jin_haihe@126.com.

內(nèi)蒙古自治區(qū)自然科學(xué)基金資助項目(2013MS0904).

許崗,金海和,劉靖.非穩(wěn)態(tài)拓?fù)湎碌臋C(jī)會網(wǎng)絡(luò)分層模型[J].東南大學(xué)學(xué)報:自然科學(xué)版,2015,45(3):438-442.

10.3969/j.issn.1001-0505.2015.03.005

TP393

A

1001-0505(2015)03-0438-05