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

許 崗 金海和,2 劉 靖

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

?

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

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

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

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

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

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

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

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

1 分層模型

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

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

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

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

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

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

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

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

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

(a) MⅠ

(b) MⅡ

(c) MⅢ

1.2 虛擬路徑

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

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

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

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

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

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

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

2.1 分層映射模型

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

2.1.1 特定場(chǎng)景

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

算法1 特定場(chǎng)景下的分層映射模型

輸入:物理移動(dòng)節(jié)點(diǎn)集J.

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

Hierarchical_Model_All_Type()

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

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

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

WhileNi.Message_Memory_STACK!=NULL

//掃描Ni消息存儲(chǔ)區(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 非特定場(chǎng)景

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

算法2 非特定場(chǎng)景下的分層映射模型

輸入:物理移動(dòng)節(jié)點(diǎn)集J,測(cè)試消息集S.

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

Hierarchical_Model_Part_Type()

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

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

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

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

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

DEQUEUE(Q1,Ni++) //取Q1隊(duì)列頭元素放入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

}

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

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

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

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

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

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

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

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

輸入:IK.

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

Map_to_graph()

{

Set(min_rtime, min_mdis, min_mtime, min_mcont)

While run_time>min_rtime //網(wǎng)絡(luò)運(yùn)行時(shí)長(zhǎng)超過(guò)給定閾值

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

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

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

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

End If

End If

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

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

End If

End While

End While

}

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

3 實(shí)驗(yàn)結(jié)果及分析

3.1 時(shí)間復(fù)雜度

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

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

1) 無(wú)并行處理情況

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

如果直接在機(jī)會(huì)網(wǎng)絡(luò)上進(jìn)行消息傳播,要進(jìn)行6c次社團(tuán)劃分,時(shí)間復(fù)雜度為6cO(n2).隨著機(jī)會(huì)網(wǎng)絡(luò)的運(yùn)行,網(wǎng)絡(luò)中傳遞的消息數(shù)量逐步增加.c隨時(shí)間不斷增大,不妨設(shè)c>n,分層模型下社團(tuán)劃分時(shí)間復(fù)雜度仍為6(O(n2)+O(n)),而直接在機(jī)會(huì)網(wǎng)絡(luò)上進(jìn)行社團(tuán)劃分的時(shí)間復(fù)雜度為6O(n3).顯然,當(dāng)n足夠大(如n=30)時(shí),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個(gè)虛擬機(jī)會(huì)網(wǎng)絡(luò)層,將w個(gè)虛擬層分解為w/b個(gè)組,每個(gè)處理器對(duì)1組虛擬層進(jìn)行社團(tuán)劃分,則時(shí)間代價(jià)為w/b(O(n2)+O(n));而直接在機(jī)會(huì)網(wǎng)絡(luò)上進(jìn)行社團(tuán)劃分的時(shí)間復(fù)雜度與消息數(shù)及消息序列類型交錯(cuò)方式相關(guān),仍為wO(n3),即wO(n3)?w/b(O(n2)+O(n))成立.

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

3.2 空間復(fù)雜度

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

3.3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

圖6 社團(tuán)劃分時(shí)間對(duì)比

4 結(jié)語(yǔ)

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

References)

[1]熊永平,孫利民,牛建偉,等. 機(jī)會(huì)網(wǎng)絡(luò)[J]. 軟件學(xué)報(bào), 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ī)會(huì)網(wǎng)絡(luò)的消息傳輸算法[J]. 計(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]彭艦, 李夢(mèng)詩(shī), 劉唐, 等. 機(jī)會(huì)網(wǎng)絡(luò)中基于節(jié)點(diǎn)社會(huì)性的數(shù)據(jù)轉(zhuǎn)發(fā)策略[J]. 四川大學(xué)學(xué)報(bào)：工程科學(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. 作者簡(jiǎn)介: 許崗(1980—)，男，博士生，講師；金海和(聯(lián)系人)，男，博士，教授，博士生導(dǎo)師, jin_haihe@126.com.

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

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

10.3969/j.issn.1001-0505.2015.03.005

TP393

A

1001-0505(2015)03-0438-05