《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計應(yīng)用 > 基于社區(qū)的機(jī)會網(wǎng)絡(luò)冗余效用混合轉(zhuǎn)發(fā)機(jī)制
基于社區(qū)的機(jī)會網(wǎng)絡(luò)冗余效用混合轉(zhuǎn)發(fā)機(jī)制
2015年微型機(jī)與應(yīng)用第8期
容振邦1,,趙鐵柱2,,計 佳1,,梁 永1
(1.五邑大學(xué) 計算機(jī)學(xué)院,廣東 江門 529020,; 2.東莞理工學(xué)院 計算機(jī)學(xué)院,廣東 東莞 523808)
摘要: 針對機(jī)會網(wǎng)絡(luò)主流路由協(xié)議沒有考慮到節(jié)點(diǎn)的社區(qū)特性,,提出了一種基于社區(qū)的冗余效用混合轉(zhuǎn)發(fā)機(jī)制,。該算法從合理降低洪泛度和準(zhǔn)確預(yù)測效用值方面出發(fā),通過消息篩選,、消息優(yōu)先級和活躍節(jié)點(diǎn)機(jī)制對消息進(jìn)行有效處理和轉(zhuǎn)發(fā),。與經(jīng)典的Epidemic和Prophet算法相比,該算法具有消息傳達(dá)率較高,、傳輸延時小和網(wǎng)絡(luò)開銷低的特點(diǎn),。
Abstract:
Key words :

  摘  要: 針對機(jī)會網(wǎng)絡(luò)主流路由協(xié)議沒有考慮到節(jié)點(diǎn)的社區(qū)特性,提出了一種基于社區(qū)的冗余效用混合轉(zhuǎn)發(fā)機(jī)制,。該算法從合理降低洪泛度和準(zhǔn)確預(yù)測效用值方面出發(fā),,通過消息篩選、消息優(yōu)先級和活躍節(jié)點(diǎn)機(jī)制對消息進(jìn)行有效處理和轉(zhuǎn)發(fā),。與經(jīng)典的Epidemic和Prophet算法相比,,該算法具有消息傳達(dá)率較高、傳輸延時小和網(wǎng)絡(luò)開銷低的特點(diǎn),。

  關(guān)鍵詞: 機(jī)會網(wǎng)絡(luò),;社區(qū);冗余效用

0 引言

  機(jī)會網(wǎng)絡(luò)是一種不需要源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間存在完整鏈路,,利用節(jié)點(diǎn)移動帶來的相遇機(jī)會實現(xiàn)通信的自組織網(wǎng)絡(luò),,其主要應(yīng)用集中在野生動物追蹤、車載網(wǎng)絡(luò),、偏遠(yuǎn)地區(qū)網(wǎng)絡(luò)傳輸?shù)葓龊蟍1],。隨著大量智能手機(jī)等手持設(shè)備的出現(xiàn),以人為載體的移動節(jié)點(diǎn)的數(shù)據(jù)交換頻繁,,逐漸出現(xiàn)以人為主體的機(jī)會網(wǎng)絡(luò),。由于人們之間社會關(guān)系相對穩(wěn)定且存在一定的依賴性,網(wǎng)絡(luò)中會出現(xiàn)節(jié)點(diǎn)的聚集現(xiàn)象,,從而形成不同的社區(qū),。社區(qū)內(nèi)的節(jié)點(diǎn)移動緩慢,相遇概率高,不同社區(qū)內(nèi)的節(jié)點(diǎn)相遇概率低,,往往需要通過一些活躍節(jié)點(diǎn)來增加社區(qū)之間的聯(lián)系,,與以節(jié)點(diǎn)移動快速、網(wǎng)絡(luò)拓?fù)渥兓l繁的普通機(jī)會網(wǎng)絡(luò)相比有明顯的區(qū)別[2],。

1 相關(guān)工作

  2006年,,MUSOLESI M等人提出了基于人類社會關(guān)系的移動自組織網(wǎng)絡(luò)移動模型,引起了人們的廣泛關(guān)注[3],。2007年,,Pan Hui等人提出為每個消息包貼上社區(qū)標(biāo)簽,轉(zhuǎn)發(fā)時只需進(jìn)行簡單的標(biāo)簽號比較就能判斷是否允許發(fā)送,,進(jìn)而提高了消息的投遞成功率[4],。2009年,牛建偉根據(jù)節(jié)點(diǎn)之間的通信頻繁程度,,自動將節(jié)點(diǎn)劃分成不同的社區(qū),,自適應(yīng)地控制消息的拷貝數(shù)量并依靠活躍節(jié)點(diǎn)將消息傳輸?shù)侥繕?biāo)社區(qū)[2]。2013年,,劉亞翃等人根據(jù)節(jié)點(diǎn)間的社會關(guān)系強(qiáng)度,,動態(tài)自適應(yīng)地將節(jié)點(diǎn)劃分為不同的社區(qū),通過限制消息副本數(shù)來減少網(wǎng)絡(luò)中消息的冗余,,并利用活躍性高的節(jié)點(diǎn)帶動消息的轉(zhuǎn)發(fā)[5],。2014年,周軍海等人提出一種基于社區(qū)的低功耗消息路由算法,,能自適應(yīng)地控制消息拷貝數(shù)量并能自動調(diào)整節(jié)點(diǎn)的活躍度,,依靠活躍度較高的節(jié)點(diǎn)來完成消息傳輸[6]。針對社區(qū)機(jī)會網(wǎng)絡(luò)的特點(diǎn),,本文提出一種基于社區(qū)的冗余效用混合轉(zhuǎn)發(fā)機(jī)制,,該算法根據(jù)現(xiàn)實社會節(jié)點(diǎn)的移動特性在傳染路由的基礎(chǔ)上對消息路由做改進(jìn),對社區(qū)內(nèi)消息包進(jìn)行優(yōu)先級分類和消息篩選,,通過活躍節(jié)點(diǎn)進(jìn)行社區(qū)間消息傳遞,,具有傳達(dá)率高、網(wǎng)絡(luò)資源消耗低,、傳輸延時小的特點(diǎn),。

2 基于社區(qū)的冗余效用混合路由算法

  機(jī)會網(wǎng)絡(luò)路由技術(shù)從不同的角度可分為不同的種類。根據(jù)路由策略來分,,可以分為基于復(fù)制的路由和基于效用的路由[7],。基于復(fù)制的路由通過洪泛的方式進(jìn)行轉(zhuǎn)發(fā),,但資源占用率高,?;谛в玫穆酚赡苡行p少過多的消息復(fù)制,但傳達(dá)率較低,,延時較大,。由于社區(qū)內(nèi)節(jié)點(diǎn)相對聚集,,不同社區(qū)之間節(jié)點(diǎn)聯(lián)系較少,,普通機(jī)會網(wǎng)絡(luò)路由算法在社區(qū)網(wǎng)絡(luò)內(nèi)效率不高。綜合以上兩種算法優(yōu)點(diǎn)的冗余效用混合路由在降低資源消耗的前提下有利于消息轉(zhuǎn)發(fā)率的提高,,在社區(qū)機(jī)會網(wǎng)絡(luò)的消息轉(zhuǎn)發(fā)機(jī)制中使用尤為合適,。算法主要包括消息篩選、優(yōu)先級和活躍節(jié)點(diǎn)3種機(jī)制,。

  2.1 消息篩選機(jī)制

  當(dāng)社區(qū)中節(jié)點(diǎn)攜帶有以本社區(qū)內(nèi)其他節(jié)點(diǎn)為目的節(jié)點(diǎn)的消息包時,,一方面,由于有社區(qū)歸屬的節(jié)點(diǎn)很大概率是在本社區(qū)內(nèi)部活動,,且社區(qū)內(nèi)節(jié)點(diǎn)間相遇頻繁,,消息包可以通過本社區(qū)的中繼節(jié)點(diǎn)經(jīng)過多跳很快傳達(dá)到目的節(jié)點(diǎn);另一方面,,外部社區(qū)的節(jié)點(diǎn)到本社區(qū)活動的概率很低,,假如把上述消息轉(zhuǎn)發(fā)給外部社區(qū)節(jié)點(diǎn),消息很有可能只會在外部社區(qū)擴(kuò)散,,很難回傳到本社區(qū),,不僅不能提高傳達(dá)率,反而盲目地增加了網(wǎng)絡(luò)中消息的副本數(shù),,增加網(wǎng)絡(luò)資源的消耗,。因此,本社區(qū)內(nèi)的消息沒有必要擴(kuò)散至其他社區(qū),。算法中加入消息篩選機(jī)制,,當(dāng)該機(jī)制檢測到相遇節(jié)點(diǎn)歸屬于不同社區(qū)且自身節(jié)點(diǎn)存儲有以同一社區(qū)內(nèi)節(jié)點(diǎn)為目的節(jié)點(diǎn)的消息包時,把該類消息包從轉(zhuǎn)發(fā)隊列中過濾掉,。

  2.2 消息優(yōu)先級機(jī)制

  由于節(jié)點(diǎn)移動的不確定性,,節(jié)點(diǎn)間從建立連接到斷開,中間的持續(xù)時間可能只是一瞬間,??紤]到網(wǎng)絡(luò)連通時間的不確定性,為了讓消息的轉(zhuǎn)發(fā)更具有效用性,,可以提前判斷消息的效用值,,按效用值由高到低順序轉(zhuǎn)發(fā)。算法加入了消息優(yōu)先級機(jī)制,,優(yōu)先級高的一類消息包優(yōu)先轉(zhuǎn)發(fā),,同類的按順序轉(zhuǎn)發(fā),。優(yōu)先級分類如下:

  (1)第一優(yōu)先級,。轉(zhuǎn)發(fā)節(jié)點(diǎn)的消息緩沖區(qū)中可能存儲有以對方節(jié)點(diǎn)為目的節(jié)點(diǎn)的消息包,,這類消息包只需要再經(jīng)過一跳就能傳達(dá)到目的節(jié)點(diǎn)。

 ?。?)第二優(yōu)先級,。在消息篩選機(jī)制中已分析到社區(qū)內(nèi)部的消息包在本社區(qū)中繼節(jié)點(diǎn)的協(xié)助下可以經(jīng)過多跳以較快的速度傳達(dá),在本社區(qū)消息不外傳的前提下,,該類消息的副本僅僅在本社區(qū)內(nèi)擴(kuò)散,,實現(xiàn)以較低的消息副本數(shù)獲得較小的傳達(dá)延時,因而該類效用值較高的消息以第二優(yōu)先級被轉(zhuǎn)發(fā),。

 ?。?)第三優(yōu)先級。轉(zhuǎn)發(fā)節(jié)點(diǎn)的消息緩沖區(qū)可能存儲有對方節(jié)點(diǎn)社區(qū)內(nèi)的消息包,,由于對方節(jié)點(diǎn)與消息目的節(jié)點(diǎn)歸屬社區(qū)相同,,那么兩節(jié)點(diǎn)很大概率在本社區(qū)內(nèi)活動,通過直接相遇或者本社區(qū)其他中繼節(jié)點(diǎn)轉(zhuǎn)發(fā),,消息可以較快傳達(dá),。

  2.3 活躍節(jié)點(diǎn)機(jī)制

  在現(xiàn)實社會,有一些人經(jīng)常穿梭于各大社區(qū)之間,,比如快遞員,、送餐員和上下班的職員等。社區(qū)間的消息可以利用這些活躍的人群進(jìn)行傳送,。這種機(jī)制讓網(wǎng)絡(luò)中的活躍節(jié)點(diǎn)承擔(dān)社區(qū)間的副本擴(kuò)散任務(wù),。其優(yōu)點(diǎn)有兩方面:一方面,控制了網(wǎng)絡(luò)中消息的洪泛程度,,避免了副本盲目,、過度地增加;另一方面,,減少不必要的傳輸,,使網(wǎng)絡(luò)資源的利用更加充分有效。

  2.4 轉(zhuǎn)發(fā)策略

  開始時,,消息發(fā)送方遇到對方節(jié)點(diǎn),,雙方建立連接。逐個遍歷緩沖區(qū)的消息,,如果滿足來自不同社區(qū)且為社區(qū)內(nèi)的消息則被篩選機(jī)制過濾掉不加入發(fā)送隊列,,否則依次經(jīng)過優(yōu)先級一、二,、三以及活躍節(jié)點(diǎn)機(jī)制進(jìn)行判斷,,符合條件則加入對應(yīng)隊列,,都不符合則放棄轉(zhuǎn)發(fā)。直到完成遍歷,,把消息依次按隊列一,、二、三和普通發(fā)送隊列給接收方,,最后結(jié)束本次任務(wù),。具體流程如圖1所示。

001.jpg

3 仿真實驗和結(jié)果分析

  3.1 模擬環(huán)境設(shè)置

  本文采用ONE模擬器為仿真平臺實現(xiàn)算法,,采用Epidemic和Prophet算法在本文設(shè)計的江門市蓬江區(qū)運(yùn)動場景中進(jìn)行對比測試,。

  3.1.1 地圖場景

  現(xiàn)實生活中,,人們的移動性強(qiáng),,社會關(guān)系復(fù)雜,移動特性各異,。為真實還原機(jī)會網(wǎng)絡(luò)的社區(qū)特性,,以江門市蓬江區(qū)16個主要社區(qū)作為仿真場景,實現(xiàn)了對真實世界移動模型的模擬,,采用OpenJUMP軟件繪制地圖,,如圖2所示。

002.jpg

  3.1.2 線路規(guī)劃

  人類社會中不同移動節(jié)點(diǎn)具有不同的偏好位置和有效活動范圍,,本文設(shè)計了機(jī)動車線路,、公交線路和社區(qū)線路,控制各類節(jié)點(diǎn)的運(yùn)動,。機(jī)動車線路限制了汽車節(jié)點(diǎn)的有效活動范圍,,公交線路上不定距離設(shè)有站點(diǎn)。

  3.1.3 節(jié)點(diǎn)規(guī)劃

  網(wǎng)絡(luò)中有人,、汽車等可以攜帶無線通信設(shè)備的移動節(jié)點(diǎn),,根據(jù)節(jié)點(diǎn)的不同移動特性設(shè)有5類節(jié)點(diǎn),具體如下:

 ?。?)普通行人節(jié)點(diǎn):只參與消息包的轉(zhuǎn)發(fā)和接收,,但不加入任何社區(qū)。

 ?。?)有社區(qū)歸屬行人節(jié)點(diǎn):大部分在本社區(qū)內(nèi)活動,。

  (3)普通汽車節(jié)點(diǎn):在機(jī)動車線路上活動,,速度快,,活動性強(qiáng)。

 ?。?)公交汽車節(jié)點(diǎn):在公交線路上移動,,緩存大,,線路固定,盡可能不調(diào)頭,。

 ?。?)動態(tài)社區(qū)歸屬節(jié)點(diǎn):在仿真范圍內(nèi)隨機(jī)活動,當(dāng)進(jìn)入某一社區(qū)就加入該社區(qū),,離開則退出該社區(qū),,用以模擬社區(qū)內(nèi)部節(jié)點(diǎn)構(gòu)成的動態(tài)變化。

  活躍節(jié)點(diǎn)來自上述部分節(jié)點(diǎn),,其中包括有社區(qū)歸屬且經(jīng)?;顒佑谄渌鐓^(qū)的節(jié)點(diǎn)、汽車節(jié)點(diǎn),、公交節(jié)點(diǎn)和動態(tài)社區(qū)歸屬行人節(jié)點(diǎn),。

  3.1.4 仿真參數(shù)

  根據(jù)以上的規(guī)劃,本文采用的仿真主要參數(shù)如表1所示,。

006.jpg

  3.2 緩存對網(wǎng)絡(luò)性能的影響

  與路由算法Epidemic和Prophet相比,,基于社區(qū)的冗余效用混合算法(用Community表示)在緩存大小不同的情況下,對消息傳達(dá)率,、平均延時和路由開銷比率3種性能指標(biāo)下影響分析如下,。

  3.2.1 消息傳遞成功率

  當(dāng)緩存較小時,網(wǎng)絡(luò)中由于消息副本量大而不能滿足消息的緩存要求,,舊的消息包會較快被新接收的擠掉,,造成大量包被丟棄,因而3種路由算法傳達(dá)率都不高,。隨著緩存容量的增大,,傳達(dá)率都有不同程度的上升。Epidemic以高傳輸延時為代價,,因而傳達(dá)率比Prophet高,。本文算法對消息副本洪泛程度控制有效,轉(zhuǎn)發(fā)效率較高,,因此傳達(dá)率較高,。具體如圖3所示。

003.jpg

  3.2.2 消息傳遞平均延時

  對于消息傳遞平均延時,,Epidemic明顯高于其他兩種算法,,由于向網(wǎng)絡(luò)中洪泛消息副本,有限的網(wǎng)絡(luò)資源會使消息包被大量丟棄,,很難找到較短傳輸路徑把消息傳到目的節(jié)點(diǎn),,傳輸延時大。Prophet和本文算法都提前對消息轉(zhuǎn)發(fā)效用值做預(yù)測,,更容易找到較短路徑,,延時較低,。具體如圖4所示。

004.jpg

  3.2.3 路由開銷比率

  從總體上看,,隨著緩存的增大,,網(wǎng)絡(luò)中節(jié)點(diǎn)的丟包量減小,更多的消息被成功傳輸,,開銷越來越低,。本文算法明顯低于Epidemic和Prophet,這是因為:一方面,,洪泛程度低,,網(wǎng)絡(luò)中消息副本較少;另一方面,,消息轉(zhuǎn)發(fā)效用高,,傳達(dá)率高,因此開銷低,。Prophet也對消息洪泛做了控制,,但由于傳達(dá)率低,,在開銷上與Epidemic相比并沒有明顯優(yōu)勢,。具體如圖5所示。

005.jpg

4 結(jié)論

  本文提出了一種基于社區(qū)的冗余效用混合傳輸機(jī)制,,目標(biāo)是解決普通機(jī)會網(wǎng)絡(luò)路由算法在社區(qū)網(wǎng)絡(luò)中性能不高的問題,。本文首先分析了目前社區(qū)機(jī)會網(wǎng)絡(luò)的研究現(xiàn)狀,針對基于復(fù)制的路由和基于效用的路由存在的問題,,提出將冗余效用混合算法應(yīng)用于基于社區(qū)的機(jī)會網(wǎng)絡(luò)中,。以江門市蓬江區(qū)為主要場景進(jìn)行了模擬,并與Epidemic和Prophet算法進(jìn)行了比較,。實驗結(jié)果表明,,冗余效用混合轉(zhuǎn)發(fā)機(jī)制在消息投遞成功率、傳遞平均延時和路由開銷比上均有明顯改善,。

參考文獻(xiàn)

  [1] 熊永平,,孫利民,牛建偉.機(jī)會網(wǎng)絡(luò)[J].軟件學(xué)報,,2009,,20(1):124-137.

  [2] 牛建偉,周興,,劉燕.一種基于社區(qū)機(jī)會網(wǎng)絡(luò)的消息傳輸算法[J].計算機(jī)研究與發(fā)展,,2009,46(12):2068-2075.

  [3] MUSOLESI M,, MASCOLO C. A community based mobility model for ad hoc network research[C]. Proceedings of the 2nd International Workshop on Multi-hop ad Hoc Networks: from Theory to Reality,, New York: ACM,, 2006: 31-38.

  [4] Pan Hui, CROWCROFT J. How small labels create big improvements[C]. Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops,,New York,,2007:65-70.

  [5] 劉亞翃,高媛,,喬晉龍.機(jī)會社會網(wǎng)絡(luò)中基于社區(qū)的消息傳輸算法[J].計算機(jī)應(yīng)用,,2013,33(5):1212-1216.

  [6] 周軍海,,林亞平,,周四望.一種低功耗的社區(qū)機(jī)會網(wǎng)絡(luò)消息路由算法[J].計算機(jī)科學(xué),2014,,41(1):178-182.

  [7] 徐佳,,王汝傳,徐杰.基于效用的容遲網(wǎng)絡(luò)路由技術(shù)研究[J].計算機(jī)應(yīng)用研究,,2011,,28(4):1211-1215.


此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載,。