考慮節(jié)點多社區(qū)屬性的機會網(wǎng)絡高吞吐量路由算法

任 智，李秀峰，王坤龍，曹紅偉

(重慶郵電大學 移動通信技術省部級重點實驗室，重慶 400065) E-mail：kcrisli@163.com

1 引 言

機會網(wǎng)絡是一種在消息源節(jié)點和目的節(jié)點之間不需要存在任何完整、持續(xù)、穩(wěn)定的通信鏈路，只利用節(jié)點的運動所創(chuàng)造的通信機會完成數(shù)據(jù)傳遞的無線自組織網(wǎng)絡[1].隨著科技的不斷發(fā)展，大量功能強大、價格低廉的智能移動設備(智能手機，便攜式電腦等)已被廣泛使用，并逐步成為未來網(wǎng)絡和服務的主體.而由人所攜帶的智能設備之間的信息傳輸都具有一定的社區(qū)屬性，鑒于這類基于社區(qū)的機會網(wǎng)絡的廣泛應用，研究基于社區(qū)的機會網(wǎng)絡路由算法已經(jīng)成為機會網(wǎng)絡研究領域的熱點之一.

社區(qū)劃分標準有很多種，最常見的劃分方法分為集中式和分布式社區(qū)劃分算法.集中式的社區(qū)劃分方法，是服務器或者網(wǎng)絡中的某個控制節(jié)點收集網(wǎng)絡中其它節(jié)點的信息并進行整理，再按照一定的標準統(tǒng)一進行社區(qū)劃分，其中具有代表性的算法是HSEO算法[2]，該算法由系統(tǒng)維護著一個模塊度Q值，首先服務器或者控制節(jié)點將網(wǎng)絡隨機分為節(jié)點等同的兩個社區(qū)，然后尋找其中對社區(qū)吸引力最小的節(jié)點移動到另一社區(qū)，由服務器或者控制節(jié)點計算此時網(wǎng)絡的模塊度Q值，重新調(diào)整節(jié)點所在社區(qū)，直到模塊度Q值不在增長，即得到了最優(yōu)的兩個社區(qū)結(jié)構(gòu)，然后依次對最優(yōu)的兩個社區(qū)結(jié)構(gòu)迭代，不斷增加需要劃分的社區(qū)數(shù)目，直到網(wǎng)絡中個社區(qū)達到穩(wěn)定.

由于在移動自組織網(wǎng)絡中，服務器不可能收集到所有節(jié)點的信息，研究者們提出了一種節(jié)點根據(jù)其本身收集到的信息劃分其所在社區(qū)的分布式社區(qū)劃分算法，其中具有代表性的算法是 CSCBR[3]，該算法通過計算一組節(jié)點兩兩間在單位時間內(nèi)的相遇次數(shù)來評價一組節(jié)點相互間的通信能力，并作為節(jié)點分簇的依據(jù)，從而達到把移動規(guī)律相近的節(jié)點聚合成簇(作者把這種簇稱為“最近社交圈”)的效果.節(jié)點成簇操作是分布式進行的，一個簇的形成需要經(jīng)過相遇權(quán)值計算、簇頭選舉和簇成員競爭3個階段，成簇之后，在簇內(nèi)和簇間會進行消息的傳送.該算法不需要某一個節(jié)點控制劃分過程和維護整個網(wǎng)絡的社區(qū)結(jié)構(gòu)，每個節(jié)點只需要維護自己的社區(qū)，后期維護社區(qū)結(jié)構(gòu)的開銷比較小.其帶來的好處就是減少了社區(qū)劃分階段和社區(qū)維護階段時大量的控制消息.

2 相關工作

基于社區(qū)的機會網(wǎng)絡的路由算法是在機會網(wǎng)絡的經(jīng)典路由算法下發(fā)展起來的，主要有以下一些路由算法.

Epidemic[4]算法是研究者們最早提出的機會網(wǎng)絡路由算法.攜帶消息的節(jié)點采用泛洪的方式將消息轉(zhuǎn)發(fā)給每個相遇節(jié)點，直至消息到達目的節(jié)點.該方式使網(wǎng)絡中的消息副本數(shù)過多，增大了整個網(wǎng)絡的開銷.ProPHET[5]算法中每個節(jié)點都維護一張與其它節(jié)點的相遇概率表，通過交換概要向量和預測概率矢量.攜帶消息的節(jié)點將消息轉(zhuǎn)發(fā)給與目的節(jié)點相遇概率更高的節(jié)點，這就大大的減少了網(wǎng)絡中該消息的副本數(shù).但是ProPHET算法沒有說明在消息被轉(zhuǎn)發(fā)目的節(jié)點后該消息在網(wǎng)絡中的副本如何消除，同時各節(jié)點無法保證計算預測概率矢量的準確性.

Label[6]算法根據(jù)用戶的興趣將機會網(wǎng)絡中的節(jié)點劃分社區(qū)，如每一個節(jié)點有不同的興趣就分配不同的Label，擁有相同的Label的節(jié)點屬于同一社區(qū).Bubble Rap[7]算法是綜合考慮了節(jié)點的中心度和社區(qū)結(jié)構(gòu)來提高消息的傳輸效率.每個節(jié)點有至少一個Label，相同Label的節(jié)點屬于同一個社區(qū).消息總是向著中心度高的節(jié)點轉(zhuǎn)發(fā)，但消息匯聚在中心度高的節(jié)點的緩存中，有可能會造成消的擁堵或者節(jié)點能量過快的消耗而死亡.STBID[8]算法節(jié)點間社會連接強度的計算機制，不同社會連接強度的節(jié)點分配有不同的用于發(fā)送數(shù)據(jù)的令牌個數(shù).SROR[9]算法和TDFSON[10]算法提供了節(jié)點社會關系的計算方法，用于在數(shù)據(jù)轉(zhuǎn)發(fā)時選擇最優(yōu)的轉(zhuǎn)發(fā)節(jié)點.

Int-Tree算法[11]假設相同興趣的節(jié)點會頻繁的相遇，攜帶消息的節(jié)點遇到與目的節(jié)點同社區(qū)的節(jié)點時，如果攜帶消息的節(jié)點也與目的節(jié)點同社區(qū)，則比較雙方節(jié)點到達目的節(jié)點的社會連接度.若對方節(jié)點的連接度更高，則轉(zhuǎn)發(fā)消息.如果攜帶消息的節(jié)點和相遇節(jié)點都與目的節(jié)點不同社區(qū)，則比較它們到目的節(jié)點的社區(qū)、目的節(jié)點的父社區(qū)以及直到根節(jié)點之間的所有父社區(qū)的密度，如果對方節(jié)點到其中任何一個社區(qū)的密度值比對應本節(jié)點到該社區(qū)的值大，則節(jié)點把數(shù)據(jù)轉(zhuǎn)發(fā)給對方節(jié)點.

BEEINFO[12]是一種基于興趣社區(qū)人工智能路由算法集合，每個節(jié)點與對應的人或者車輛具有相同的社會特性和移動規(guī)律.網(wǎng)絡中的節(jié)點根據(jù)自身的興趣劃分為不同的社區(qū)，BEEINFO主要是充分利用個人的學習能力和相互合作來感知環(huán)境的動態(tài)變化，該算法可以根據(jù)環(huán)境的不同可以分為三種不同的算法：BEEINFO-D、BEEINFO-S和BEEINFO-D&S.BEEINFO-D算法的思路是消息在社區(qū)間傳遞時主要利用社區(qū)密度作為轉(zhuǎn)發(fā)參數(shù)，在社區(qū)內(nèi)部時，由攜帶消息的節(jié)點直接將消息投遞給目的節(jié)點；BEEINFO-S算法的思路是消息在社區(qū)間傳遞時，源節(jié)點只把消息轉(zhuǎn)發(fā)給目的社區(qū)內(nèi)的節(jié)點.當消息轉(zhuǎn)發(fā)到目的節(jié)點后，根據(jù)節(jié)點與目的節(jié)點的社會連接度大小轉(zhuǎn)發(fā)消息；BEEINFO-D&S算法利用社會密度信息幫助節(jié)點在社區(qū)間轉(zhuǎn)發(fā)消息，利用社會連接度信息幫助節(jié)點在社區(qū)內(nèi)部轉(zhuǎn)發(fā)消息.

在深入研究基于社區(qū)的機會網(wǎng)絡路由算法后，發(fā)現(xiàn)現(xiàn)有基于興趣劃分社區(qū)的算法存在沒有考慮節(jié)點多社區(qū)屬性、統(tǒng)計節(jié)點相遇次數(shù)不夠準確和相遇節(jié)點間控制信息冗余的問題.為解決以上問題，本文提出一種考慮節(jié)點多社區(qū)屬性的機會網(wǎng)絡高效路由算法—HRCMA，并從理論分析和仿真驗證了所提算法的有效性.

3 系統(tǒng)模型與問題描述

3.1 系統(tǒng)模型

本文以行人所攜帶的智能設備(如手機)為網(wǎng)絡節(jié)點，具有相同興趣的人(例如同學或同事)通常會聚在一起討論并分享他們的興趣，他們經(jīng)常聯(lián)系并組成一個社區(qū).這些利益相關的社區(qū)與地區(qū)保持一致，在利益上彼此不同.此外，不同興趣每天都會生成大量不同的數(shù)據(jù)，通常用不同的標簽標記以表示其類別.因此網(wǎng)絡節(jié)點使用不同數(shù)據(jù)類別來代表人們的興趣對社區(qū)進行劃分，一個社區(qū)與一個類別有關.對于一個特定的社區(qū)，如果一個人對該類別感興趣，則對應節(jié)點屬于該社區(qū)；如果他有多個興趣，他同時屬于并影響到幾個社區(qū).毫無疑問，多重興趣比單一興趣更復雜，本文系統(tǒng)模型為多興趣網(wǎng)絡模型.

定義1.移動模型：機會網(wǎng)絡中的節(jié)點具有一定的社會性，其運動并不是完全隨機的，經(jīng)常相遇的節(jié)點之間有一個較高的接觸概率，在未來相遇的可能性也較大.

定義2.社區(qū)密度：社區(qū)密度可以用節(jié)點在時間窗口T內(nèi)所遇到的某一個社區(qū)i內(nèi)節(jié)點的次數(shù)n表示，在BEEINFO算法中，社區(qū)密度計算公式如1，而公式2是對該社區(qū)未來密度的預測.

(1)

Densityi(t+Δt)=α×Densityi(t-Δt)+(1-α)×Densityi(t)

(2)

式中，α是社區(qū)密度的預測因子，表明過去密度信息和現(xiàn)在密度信息的影響權(quán)重.

如果當前節(jié)點長時間沒有與某社區(qū)內(nèi)的節(jié)點相遇，則該社區(qū)的密度也會逐漸降低，計算公式如(3)所示：

Densitynew(t)=Densityold×γk

(3)

式中，γ是衰退指數(shù)，k是距離上次更新的時間間隔.

定義3.社會連接度：用來表示相同社區(qū)(興趣)的節(jié)點之間社會關系的強弱.節(jié)點的社會連接度信息只能在社區(qū)內(nèi)部發(fā)揮作用.在BEEINFO算法中，社會連接度計算公式如公式(4)，而公式(5)是對未來社會連接度的預測.

SoTiei，j(t)=(λi，j×di，j(t))/T

(4)

SoTiei，j(t+Δt)=β×SoTiei，j(t-Δt)+(1-β)×SoTiei，j(t)

(5)

式中，λi，j是接觸頻率(在時間窗口T內(nèi)，節(jié)點i與j的相遇次數(shù))，di，j是在時間窗口T內(nèi)節(jié)點i與j的接觸時間，β是預測因子.

隨著節(jié)點之間長時間未相遇，節(jié)點之間的連接度也會不斷減小.

SoTienew=SoTieold×γk

(6)

定義4.節(jié)點親密度：在節(jié)點多興趣模型中，用來表示節(jié)點間的親密程度.當兩節(jié)點無共同的興趣時，節(jié)點親密度計算公式如公式(7)所示，當兩節(jié)點存在共同的興趣時，節(jié)點節(jié)點親密度計算公式如公式(8)所示.

(7)

(8)

3.2 問題描述

通過研究發(fā)現(xiàn)，現(xiàn)有的以BEEINFO算法為代表的基于興趣劃分的社區(qū)網(wǎng)絡存在以下3個問題：

3.2.1 節(jié)點多社區(qū)屬性問題

在BEEINFO算法中，作者假設節(jié)點只有單一興趣，即只屬于某一社區(qū)，然后利用相遇節(jié)點雙方與目的節(jié)點的社區(qū)關系進行轉(zhuǎn)發(fā)選擇，沒有考慮現(xiàn)實中節(jié)點同時屬于多個社區(qū)的情況，從而縮小了轉(zhuǎn)發(fā)節(jié)點的選擇范圍，數(shù)據(jù)包的轉(zhuǎn)發(fā)機會受到抑制，對數(shù)據(jù)傳送成功率和吞吐量有不利影響.

3.2.2 節(jié)點相遇歷史中存在無效相遇情況

BEEINFO算法在數(shù)據(jù)轉(zhuǎn)發(fā)時主要依賴兩個參數(shù)：社區(qū)密度和社會連接度.這兩個參數(shù)在節(jié)點相遇后的更新過程如圖1所示，在兩個相遇節(jié)點相互交換興趣信息和消息摘要列表后，如果兩個節(jié)點處于不同社區(qū)，則更新它們所記錄的對方社區(qū)的密度信息(UpdateDensity).否則，更新它們所記錄的本社區(qū)密度信息(UpdateDensity)和對方節(jié)點的社會連接度信息(UpdateSocTie).

圖1 節(jié)點相遇后更新的過程Fig.1 Update process after node’s encounter

BEEINFO算法在統(tǒng)計節(jié)點之間相遇歷史次數(shù)時沒有考慮無效相遇的情況，而無效相遇會對數(shù)據(jù)轉(zhuǎn)發(fā)所依據(jù)的社會連接度和社區(qū)密度兩個參數(shù)造成虛高的不利影響，虛高的社會連接度和社區(qū)密度值使得鄰居節(jié)點向其轉(zhuǎn)發(fā)更多的消息，但是該節(jié)點到達目的節(jié)點或社區(qū)的消息轉(zhuǎn)發(fā)能力可能低于實際情況，從而造成數(shù)據(jù)傳遞成功率的降低和傳輸時延的增大.

3.2.3 控制消息存在冗余

在BEEINFO所研究的節(jié)點單社區(qū)模型中，兩個節(jié)點成為鄰居后，需要交換各自的興趣I(用以標識各自的社區(qū))和消息摘要列表Lm(本節(jié)點攜帶的所有消息摘要)，然后根據(jù)消息目的節(jié)點的興趣，發(fā)送給對方自己記錄的目的社區(qū)的密度信息或目的節(jié)點的社會連接度信息，最后選擇目的社區(qū)密度大或者與目的節(jié)點社會連接度大的節(jié)點攜帶該消息.但是在其中一個節(jié)點收到對方的興趣后，可以在要發(fā)送的消息摘要列表中刪掉肯定不會轉(zhuǎn)發(fā)給對方的消息的摘要信息.也可以在一個節(jié)點收到對方興趣消息和請求消息后，減少要發(fā)送的請求消息中對方節(jié)點肯定會轉(zhuǎn)發(fā)給自己的消息的請求內(nèi)容.通過縮減這些控制消息可以減少網(wǎng)絡資源的消耗，提高消息轉(zhuǎn)發(fā)效率.

4 HRCMA算法

針對上邊所述的3個問題，本章提出一種新的HRCMA算法.HRCMA算法增加了節(jié)點多社區(qū)屬性的消息轉(zhuǎn)發(fā)策略，通過篩選掉節(jié)點間的無效相遇和精簡控制消息的內(nèi)容來提高消息轉(zhuǎn)發(fā)效率.

4.1 HRCMA算法新機制

4.1.1 節(jié)點多社區(qū)屬性的消息轉(zhuǎn)發(fā)策略

節(jié)點A，B相遇后，相互交換興趣信息In(表示當前節(jié)點所屬的社區(qū)集合)和消息摘要列表Lm(所攜帶的消息的摘要信息)，通過In+Lm 信息判斷是否向?qū)Ψ教岢鱿⑥D(zhuǎn)發(fā)請求，判斷策略如下：

假設A節(jié)點的消息列表Lm中的消息M，其目的節(jié)點為D，所屬社區(qū)集SD={S1，S2，S3…}；

1)如果節(jié)點A所屬社區(qū)集SA與SD互異，即SA∩SD=?，而節(jié)點B所屬社區(qū)集SB與SD有相同子集，即SB∩SD≠?，則節(jié)點A將消息M轉(zhuǎn)發(fā)給節(jié)點B；反之，若SA∩SD≠?而SB∩SD=?，則不轉(zhuǎn)發(fā)該消息.

2)如果節(jié)點A，B的社區(qū)集SA，SB都與SD互異，即SA∩SD=?且SB∩SD=?，各節(jié)點計算與目的節(jié)點的親密度，根據(jù)公式(7)計算得到IntimacyA，D和IntimacyB，D，通過相互發(fā)送REQIntimacy得知彼此與目的節(jié)點的親密度，比較親密度的大小，若IntimacyB，D>IntimacyA，D，則A轉(zhuǎn)發(fā)該消息，否則不轉(zhuǎn)發(fā).

3)如果節(jié)點A，B都與節(jié)點D存在相同的興趣，即SA∩SD≠?且SB∩SD≠?，則同樣比較A，B節(jié)點與目的D的親密度，根據(jù)公式(8)計算IntimacyA，D和IntimacyB，D，相互發(fā)送REQIntimacy得知彼此與目的節(jié)點的親密度，若IntimacyB，D>IntimacyA，D，則A轉(zhuǎn)發(fā)該消息，否則不轉(zhuǎn)發(fā).

4.1.2 節(jié)點無效相遇的判斷機制

節(jié)點A和B相互收到hello消息確定鄰居關系，之后判斷A、B相遇是否有效的機制如下：

1)判斷A、B節(jié)點是否收到對方發(fā)送的數(shù)據(jù).如果收到對方發(fā)送的數(shù)據(jù)，則此次相遇有效.否則，跳到(2).

2)判斷在上次收到對方消息后的一個hello周期內(nèi)是否第二次收到對方的hello消息.如果收到，則此次相遇有效.否則，跳到(3).

3)判斷是否收到對方的請求消息REQDensity or SocTie(請求消息的內(nèi)容是節(jié)點記錄的對方發(fā)送來的Lm中自己感興趣的消息的目的節(jié)點的社會連接度或者目的社區(qū)的社區(qū)密度)或REQIntimacy.如果收到了，則此次相遇有效.否則，跳到(4).

4)判斷是否收到In+Lm，如果沒有收到，則此次相遇為無效相遇，否則，跳到(5).

5)判斷A、B的運動方向.根據(jù)節(jié)點第一次收到對方發(fā)來的hello包和In+Lm包，采用接收信號強度指數(shù)(RSSI)測距機制[13]計算A與B節(jié)點之間的距離，從而判斷兩個節(jié)點是相互靠近還是相互遠離.如果兩個節(jié)點相互靠近，則此次相遇有效；如果相互遠離，則此次相遇無效.

4.1.3 精簡控制消息

在節(jié)點單社區(qū)模型中，相遇節(jié)點交互過程如圖2所示.圖中REQDensity or SocTie在節(jié)點i與j不同社區(qū)時是REQDensity，在節(jié)點i和j同社區(qū)時是REQSocTie.但是在i先收到對方的Ij+Lmj后，之后再發(fā)送的Ii+Lmi和REQ(i)Density or SocTie長度是可以縮減的，同時REQ(j)Density or SocTie也可以縮減.

圖2 相遇節(jié)點之間的交互過程Fig.2 Interaction process between nodes

1)Ii+Lmi

在節(jié)點i收到Ij+Lmj后獲知節(jié)點j所屬的社區(qū)，如果節(jié)點i和j不在同一個社區(qū)，由于同社區(qū)內(nèi)的節(jié)點之間相遇的概率比社區(qū)間的節(jié)點相遇概率大，所以Lmi中不必攜帶節(jié)點i緩存中與i同社區(qū)的消息的摘要信息，只需要發(fā)送L(m-m＇)i(m＇表示節(jié)點i緩存中所有目的節(jié)點與i同社區(qū)的消息集合).同理，該策略可以應用于節(jié)點多社區(qū)模型，在節(jié)點i收到Inj+Lmj后，若緩存中存在目的節(jié)點社區(qū)集與節(jié)點j所屬社區(qū)集互異而與本節(jié)點所屬社區(qū)集有相同子集的消息時，可以在發(fā)送Lmi時從列表中去掉這部分消息.

2)REQDensity orSocTie

兩個節(jié)點成為鄰居后，節(jié)點i收到對方j發(fā)送的Ij+Lmj消息，獲知自己、節(jié)點j和消息M(M是mj中的任意一個消息)的目的節(jié)點d之間的社區(qū)關系；如果節(jié)點i又收到REQ(j)Density or SocTie，則節(jié)點i可以確定節(jié)點j也收到了自己發(fā)送的Ij+Lmj，并據(jù)此判斷是否減少REQ(i)Density or SocTie中所包含的信息.同理，節(jié)點j收到節(jié)點i的Ii+Lmi消息后，可以采用同樣的策略減少REQ(j)Density or SocTie消息的內(nèi)容.以節(jié)點i收到節(jié)點j的Ij+Lmj消息和REQ(j)Density or SocTie消息的情況為例，判斷是否減少REQ(i)Density or SocTie中消息M的請求信息的過程如下：

a)如果節(jié)點i與節(jié)點j都與節(jié)點d同社區(qū)，則REQ(i)Density or SocTie包含消息M的請求信息.

b)如果節(jié)點i與節(jié)點d同社區(qū)，節(jié)點j與節(jié)點d不同社區(qū)，則REQ(i)Density or SocTie中就刪除消息M的請求信息，只發(fā)送REQ＇(i)Density or SocTie，因為即使節(jié)點i不向節(jié)點j請求消息M，節(jié)點j也會把消息M轉(zhuǎn)發(fā)給節(jié)點i.

c)如果節(jié)點i與節(jié)點j都不與節(jié)點d同社區(qū)，則REQ(i)Density or SocTie包含消息M的請求信息.

同理，在節(jié)點多社區(qū)模型中，可以采用該策略，若節(jié)點j攜帶的消息M的目的節(jié)點社區(qū)集與節(jié)點j所屬社區(qū)集互異而與節(jié)點i所屬社區(qū)集有相同子集時，節(jié)點i可以在發(fā)送REQ(i)Intimacy時刪除對消息M的請求信息.

4.2 HRCMA算法步驟

采用HRCMA算法的節(jié)點A判斷節(jié)點A，B相遇情況及消息交互的操作步驟如下：

1)節(jié)點A收到B發(fā)送的hello消息后，確定節(jié)點B為鄰居節(jié)點；

2)判斷是否收到InB+LmB(節(jié)點B發(fā)送).如果收到，則向節(jié)點B發(fā)送改進后的InA+L(m-m＇)A；否則發(fā)送InA+LmA，并等待接收InB+LmB.

3)判斷收到REQ(B)Density or SocTie或REQ(B)Intimacy？如果收到，則向節(jié)點B發(fā)送改進后的REQ′(A)Density or SocTie或REQ′(A)Intimacy；否則發(fā)送REQ(A)Density or SocTie或REQ(A)Intimacy，并等待接收REQ(B)Density or SocTie或REQ(B)Intimacy.

4)根據(jù)節(jié)點B發(fā)送的REQ(B)Density or SocTie或REQ(B)Intimacy，通過判斷選出要發(fā)送給節(jié)點B的數(shù)據(jù)并發(fā)送.等待接收節(jié)點B的數(shù)據(jù).

5)通過控制消息的交互，結(jié)合節(jié)點無效相遇判斷機制判斷本次相遇是否為有效相遇，并根據(jù)判斷結(jié)果更新到節(jié)點B所在社區(qū)的社區(qū)密度和與節(jié)點B的社會連接度.

5 HRCMA算法仿真驗證

本節(jié)利用ONE仿真平臺對HRCMA算法的相關性能進行仿真驗證，并與BEEINFO、Epidemic和ProPHET算法對比相關性能的優(yōu)劣.

5.1 仿真統(tǒng)計量的定義

1)吞吐量：吞吐量是指在單位時間內(nèi)成功送達的消息的比特數(shù).計算公式為：

π=P/T

(9)

式中，π表示吞吐量；P表示成功送達的消息的比特數(shù)；T表示運行時間.

2)歸一化控制開銷：歸一化控制開銷表示網(wǎng)絡中所有控制消息總比特數(shù)所占比例，公式如下：

η=Nc/(Ng+Nd)

(10)

式中，Nc為所有控制消息的總比特數(shù)，Ng為到達目的節(jié)點的控制消息的總比特數(shù)，Nd為到達目的節(jié)點的數(shù)據(jù)消息的總比特數(shù).

3)消息傳輸成功率：消息傳輸成功率是指成功投遞到目的節(jié)點的消息數(shù)量與網(wǎng)絡中源節(jié)點產(chǎn)生的消息(不含副本)的數(shù)量的比值，公式如下：

(11)

式中，D表示成功投遞到目的節(jié)點的消息的總數(shù)，C表示源節(jié)點產(chǎn)生的所有消息的總數(shù).

4)平均端到端時延：平均端到端時延表示從消息產(chǎn)生的時刻到該消息被成功投遞到目的節(jié)點的時刻的時間均值，公式如下：

(12)

式中，Ti表示第i個被成功投遞到目的節(jié)點的消息從產(chǎn)生到被投遞到目的節(jié)點的時間間隔，D表示所有被成功投遞到目的節(jié)點的消息數(shù)量的總數(shù).

5.2 網(wǎng)絡場景及參數(shù)設置

HRCMA算法的仿真地圖場景為ONE仿真軟件默認的芬蘭赫爾辛基市地圖，仿真場景的相關參數(shù)設置如下表1所示：

5.3 仿真結(jié)果及分析

5.3.1 網(wǎng)絡吞吐量

圖3顯示的是網(wǎng)絡吞吐量對比圖.由圖可知，各算法消息網(wǎng)絡吞吐量隨節(jié)點緩存增長而增長，相比于BEEINFO算法，HRCMA算法在網(wǎng)絡吞吐量上提高了至少3.26%(節(jié)點緩存為50M時，(380-368)/368=3.26%)，這是因為HRCMA算法增加了多個社區(qū)的情形，將節(jié)點親密度作為多社區(qū)情形下轉(zhuǎn)發(fā)消息的度量，與目的節(jié)點具有部分相同興趣的節(jié)點會參與消息的轉(zhuǎn)發(fā)，因此網(wǎng)絡中被轉(zhuǎn)發(fā)的消息數(shù)量得到有效提升，網(wǎng)絡吞吐量更高，同時HRCMA算法的節(jié)點間的相遇次數(shù)更可靠，選擇的轉(zhuǎn)發(fā)節(jié)點能轉(zhuǎn)發(fā)該消息的概率更大，進而網(wǎng)絡吞吐量得到提高.

表1 仿真場景參數(shù)Table 1 Simulation scene parameters

5.3.2 消息投遞成功率

圖4顯示的是投遞成功率對比圖.由圖可知，各算法消息投遞成功率與節(jié)點緩存呈正相關，因為節(jié)點的緩存增大，節(jié)點攜帶消息的副本數(shù)增加，緩存容量丟包概率降低.相比于BEEINFO算法，HRCMA算法在投遞概率上提高了至少2.81%(節(jié)點緩存為50M時，(73-71)/70=2.81%)，這是因為HRCMA算法考慮了節(jié)點可能屬于多個社區(qū)的情形，增加了節(jié)點親密度作為轉(zhuǎn)發(fā)消息的度量，在HRCMA算法中與目的節(jié)點具有部分相同興趣的節(jié)點也會協(xié)助轉(zhuǎn)發(fā)消息，因此節(jié)點轉(zhuǎn)發(fā)的概率更高，同時HRCMA算法統(tǒng)計的節(jié)點間的相遇次數(shù)更可靠，改進后計算得到的社區(qū)密度和節(jié)點社會連接度及節(jié)點親密度更能體現(xiàn)節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)的能力，選擇的轉(zhuǎn)發(fā)節(jié)點成功投遞該消息的概率更大.

圖3 網(wǎng)絡吞吐量對比Fig.3 Comparison of throughput圖4 投遞成功率對比Fig.4 Comparison of succeed delivery rate

5.3.3 歸一化控制開銷

圖5所示的是歸一化控制開銷對比圖.由仿真結(jié)果可以看出，歸一化控制開銷隨著節(jié)點緩存的增加逐漸減小，因為網(wǎng)絡中控制消息總比特數(shù)未變，但節(jié)點緩存增加會提高投遞成功率，使得到達目的節(jié)點的比特數(shù)增加.HRCMA算法比BEEINFO算法的歸一化開銷至少減低6.1%(緩存為10M時，(0.65-0.61)/0.65=6.1%)，其原因是，在每次節(jié)點相遇時，HRCMA算法通過兩個節(jié)點之間交互的控制消息的信息和順序，縮減它們之間之后需要交換的In+Lm和REQ控制消息的內(nèi)容.同時，統(tǒng)計節(jié)點相遇次數(shù)時，去除不能傳輸數(shù)據(jù)的相遇情況，消息的投遞概率更高.

圖5 歸一化控制開銷對比Fig.5 Comparison of normalized control overhead圖6 消息投遞平均時延對比Fig.6 Comparison of transmission delay

5.3.4 平均端到端的時延

圖6顯示的是消息投遞平均時延對比圖.HRCMA和BEEINFO算法相比，節(jié)點緩存在10MB到20MB之間時，平均端到端時延略有降低；而節(jié)點緩存在20MB到50MB之間時，HRCMA算法的平均端到端的時延和BEEINFO算法相比至少降低0.5%(節(jié)點緩存為20M時，(5650-5620)/5650=0.5%)，主要是因為HRCMA算法考慮了節(jié)點可能屬于多個社區(qū)的情形，在該情形下，與目的節(jié)點具有部分相同興趣的節(jié)點個數(shù)高于BEEINFO算法中與目的節(jié)點同社區(qū)的節(jié)點個數(shù)，因此節(jié)點轉(zhuǎn)發(fā)的概率更高，同時HRCMA算法統(tǒng)計的是節(jié)點相遇且能夠傳輸數(shù)據(jù)的相遇歷史，據(jù)此選擇出的轉(zhuǎn)發(fā)節(jié)點可以更快的把數(shù)據(jù)轉(zhuǎn)發(fā)給下一個可以轉(zhuǎn)發(fā)的節(jié)點甚至目的節(jié)點.

6 結(jié) 論

本文在針對基于興趣劃分社區(qū)的路由算法存在的問題，提出了考慮節(jié)點多社區(qū)屬性的機會網(wǎng)絡高效路由算法——HRCMA.通過仿真驗證了HRCMA算法在消息的吞吐量、控制開銷、投遞成功率、傳輸延時等方面的優(yōu)越性.在未來研究中，將以HRCMA算法為基礎，設計更為節(jié)能的路由算法，構(gòu)建綠色低能耗的社區(qū)網(wǎng)絡.