基于機(jī)會(huì)網(wǎng)絡(luò)的資源共享路由策略研究與仿真

戚 娜

(陜西工業(yè)職業(yè)技術(shù)學(xué)院信息工程學(xué)院，陜西 咸陽(yáng) 712000)

0 引言

隨著大規(guī)模集成電路和智能手持設(shè)備的快速發(fā)展，手機(jī)等無(wú)線通信設(shè)備已經(jīng)遍布在人們的生活環(huán)境中。當(dāng)人們攜帶這些通訊設(shè)備移動(dòng)的同時(shí)，通訊設(shè)備之間利用其短距離無(wú)線通訊接口可自組成在節(jié)點(diǎn)之間交換和共享信息的機(jī)會(huì)網(wǎng)絡(luò)［1］。機(jī)會(huì)網(wǎng)絡(luò)類似于傳統(tǒng)的Ad hoc［2］網(wǎng)絡(luò)，即網(wǎng)絡(luò)中無(wú)需固定的基礎(chǔ)通信設(shè)施，節(jié)點(diǎn)之間利用各自移動(dòng)所帶來(lái)的相遇機(jī)會(huì)與隨機(jī)的鄰居節(jié)點(diǎn)進(jìn)行通信［3］。由于機(jī)會(huì)網(wǎng)絡(luò)具有無(wú)中心、自組織、部署方便、可移動(dòng)和多跳等特點(diǎn)［4］，被廣泛地應(yīng)用于各個(gè)領(lǐng)域，例如區(qū)域數(shù)據(jù)共享、稀疏軍事網(wǎng)絡(luò)、受災(zāi)地區(qū)和通信困難的環(huán)境中等［5］。

無(wú)線通訊的飛速發(fā)展和信息的日益豐富，使得資源共享成為機(jī)會(huì)網(wǎng)絡(luò)中重要的應(yīng)用［6］。尤其是在偏遠(yuǎn)地區(qū)和惡劣環(huán)境中，例如地震等災(zāi)難發(fā)生以后，由于其網(wǎng)絡(luò)基礎(chǔ)設(shè)施的稀少和癱瘓導(dǎo)致傳統(tǒng)的蜂窩網(wǎng)絡(luò)和Internet 網(wǎng)絡(luò)中斷［7］，而一些重要的信息則可以通過(guò)節(jié)點(diǎn)之間自組的機(jī)會(huì)網(wǎng)絡(luò)進(jìn)行傳輸［8］。由于節(jié)點(diǎn)移動(dòng)具有地域限制性，機(jī)會(huì)網(wǎng)絡(luò)往往不能將消息傳輸?shù)胶苓h(yuǎn)的地方，所以網(wǎng)絡(luò)的通信區(qū)域也具有限制性［9］。正是如此，利用機(jī)會(huì)網(wǎng)絡(luò)建立起固定區(qū)域范圍內(nèi)的資源共享網(wǎng)絡(luò)具有重要的意義［10］。例如在災(zāi)難環(huán)境下社區(qū)內(nèi)實(shí)現(xiàn)實(shí)時(shí)災(zāi)情通報(bào)、在校園內(nèi)的移動(dòng)學(xué)習(xí)資源實(shí)時(shí)分享、地區(qū)內(nèi)的通知公告、天氣預(yù)報(bào)等信息發(fā)布和共享。

機(jī)會(huì)網(wǎng)絡(luò)中沒(méi)有專用的路由器、服務(wù)器以及接入點(diǎn)等基礎(chǔ)設(shè)施，網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)都可以充當(dāng)數(shù)據(jù)轉(zhuǎn)發(fā)設(shè)備的角色［11］。因此，機(jī)會(huì)網(wǎng)絡(luò)技術(shù)中路由協(xié)議是一個(gè)很重要的研究熱點(diǎn)，經(jīng)典的機(jī)會(huì)網(wǎng)絡(luò)路由算法如epidmic 等沒(méi)有考慮資源共享網(wǎng)絡(luò)的特性，只是以洪泛的形式共享消息，容易造成網(wǎng)絡(luò)負(fù)載加大和資源浪費(fèi)［12］。本文提出一種針對(duì)于資源共享網(wǎng)絡(luò)的路由算法，該算法充分考慮消息的有效范圍、目的節(jié)點(diǎn)簇以及根據(jù)其生命周期和在網(wǎng)絡(luò)中的潛在價(jià)值，使得在固定區(qū)域范圍內(nèi)的資源共享網(wǎng)絡(luò)的性能有明顯的提升。

1 網(wǎng)絡(luò)及信息屬性

對(duì)于需要共享的資源而言，一般會(huì)有一定的關(guān)系或者地理上的共享范圍，不同的資源僅僅在具有特定關(guān)系范圍的節(jié)點(diǎn)之間有價(jià)值或者在地區(qū)范圍內(nèi)的節(jié)點(diǎn)之間有效［13］。例如居民社區(qū)內(nèi)的通知、知識(shí)普及等內(nèi)容將會(huì)在社區(qū)內(nèi)有效傳播;學(xué)校內(nèi)的不同學(xué)科的網(wǎng)絡(luò)課堂視頻、作業(yè)等將會(huì)在不同專業(yè)的人群中傳播。對(duì)于此類消息適用范圍之外的節(jié)點(diǎn)而言，無(wú)效的資源不但沒(méi)有利用價(jià)值，還會(huì)浪費(fèi)緩存、能耗等甚至造成其網(wǎng)絡(luò)擁塞，傳輸性能下降。

圖1 消息錨區(qū)示意圖

共享資源需要保證其保密性和安全性［14］。例如，一個(gè)固定組織內(nèi)的重要通知、重要文件等，只可以在組織內(nèi)部傳播，而組織之外的人無(wú)法獲取到資源內(nèi)容?；诖耍诒疚闹卸x共享資源消息的一些特有屬性:

1)消息的目的節(jié)點(diǎn)簇。指一個(gè)消息將要分享給指定的目的節(jié)點(diǎn)集合，即此消息只能在消息的節(jié)點(diǎn)簇集合內(nèi)有效分享和傳播，而消息對(duì)于目的節(jié)點(diǎn)簇集合之外的節(jié)點(diǎn)是無(wú)效的。

2)消息的錨區(qū)。指消息的地理有效范圍，即只要在消息的錨區(qū)內(nèi)，此消息就是有效的，可以被有效地分享和轉(zhuǎn)發(fā)至其他節(jié)點(diǎn)。圖1 中，消息的錨區(qū)可以是實(shí)線區(qū)域以內(nèi)，即消息在實(shí)線區(qū)域內(nèi)是有效的。

3)消息的優(yōu)先級(jí)。指消息在網(wǎng)絡(luò)中傳播的優(yōu)先等級(jí)，節(jié)點(diǎn)創(chuàng)建消息時(shí)根據(jù)其重要程度，為其指定具體的優(yōu)先等級(jí)，優(yōu)先級(jí)分為1～5 的5 個(gè)級(jí)別。例如，在地區(qū)性天氣預(yù)報(bào)預(yù)警通知中，可以根據(jù)緊急程度指定不同的優(yōu)先級(jí)別。

4)消息的生命周期。指消息從創(chuàng)建開(kāi)始，在網(wǎng)絡(luò)中有效的時(shí)間。例如，具體的課程作業(yè)、通知等都有時(shí)間有效性。過(guò)了消息生命周期以后，此消息將被網(wǎng)絡(luò)中所有節(jié)點(diǎn)刪除，以節(jié)省網(wǎng)絡(luò)中的緩存等資源。

2 資源分享路由方案

2.1 消息調(diào)度策略

消息調(diào)度策略的任務(wù)是為每個(gè)節(jié)點(diǎn)處理將要發(fā)送消息隊(duì)列的順序。為了保證重要的消息能以最快速度分享到網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)或者在緩存不足的情況下不被首先刪除，根據(jù)消息的優(yōu)先級(jí)和生命周期，建立資源共享網(wǎng)絡(luò)中消息的綜合權(quán)重計(jì)算公式和節(jié)點(diǎn)之間傳輸消息隊(duì)列的調(diào)度算法。

假設(shè)消息m 的優(yōu)先級(jí)別為Pm，生命周期為Tmax，則消息m 在節(jié)點(diǎn)消息隊(duì)列中隨時(shí)間的權(quán)重變化為:

從式(1)中可以看出，該消息的權(quán)重算法的思想是每個(gè)消息的權(quán)重會(huì)隨著時(shí)間衰減，當(dāng)生命周期結(jié)束以后，消息的權(quán)重衰減為0。

在每個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)消息時(shí)，消息隊(duì)列的調(diào)度算法思想是將消息隊(duì)列中的消息按照即時(shí)權(quán)重從高到低的順序依次轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)，具體消息權(quán)重調(diào)度算法偽碼如下:

2.2 消息轉(zhuǎn)發(fā)策略

機(jī)會(huì)網(wǎng)絡(luò)利用節(jié)點(diǎn)相遇所帶來(lái)的通信機(jī)會(huì)傳輸消息，在不依靠固定設(shè)施的前提下，使網(wǎng)絡(luò)中的節(jié)點(diǎn)快速高效地分享資源。本節(jié)中，建立起充分考慮地域范圍和目的簇以及消息優(yōu)先權(quán)重的路由算法，稱之為sharing 路由算法。

sharing 路由算法的思想是，當(dāng)節(jié)點(diǎn)在網(wǎng)絡(luò)中移動(dòng)時(shí)，會(huì)隨機(jī)與鄰居節(jié)點(diǎn)相遇，相遇之后節(jié)點(diǎn)之間開(kāi)始相互向?qū)Ψ睫D(zhuǎn)發(fā)消息。首先節(jié)點(diǎn)會(huì)按照2.1 節(jié)所提出的調(diào)度策略對(duì)發(fā)送消息隊(duì)列中的消息進(jìn)行優(yōu)先排序，然后將消息隊(duì)列中的消息依次轉(zhuǎn)發(fā)，在轉(zhuǎn)發(fā)的過(guò)程中，每個(gè)消息又有以下3 種情況:

1)假設(shè)節(jié)點(diǎn)對(duì)處于消息的錨區(qū)內(nèi)，此時(shí)消息對(duì)于目的節(jié)點(diǎn)是有效的，為了將信息快速地在網(wǎng)絡(luò)中分享，節(jié)點(diǎn)之間采用洪泛的轉(zhuǎn)發(fā)模式，即直接將消息的副本轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。假設(shè)在校園內(nèi)分享學(xué)習(xí)資源，所有在校園內(nèi)的節(jié)點(diǎn)可以最快的速度獲取所需信息。

2)假設(shè)節(jié)點(diǎn)對(duì)處于消息的錨區(qū)之外，為了保證消息發(fā)送的有效性和安全性，此時(shí)需要判斷鄰居節(jié)點(diǎn)是否屬于消息的目的簇之內(nèi)，如果屬于目的簇，則將消息的副本轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。例如在社區(qū)通知消息的共享中，圖1 中的鄰居節(jié)點(diǎn)A 雖然不在實(shí)線社區(qū)內(nèi)，但是該成員屬于社區(qū)通知消息的目的簇節(jié)點(diǎn)內(nèi)，依然可以在社區(qū)外通過(guò)節(jié)點(diǎn)的相遇接收到消息。

3)假設(shè)節(jié)點(diǎn)對(duì)處于消息的錨區(qū)之外且鄰居節(jié)點(diǎn)不屬于消息的目的簇節(jié)點(diǎn)內(nèi)，則不轉(zhuǎn)發(fā)此消息，此時(shí)發(fā)送節(jié)點(diǎn)跳過(guò)本消息后判斷隊(duì)列中下一條消息。例如在遇到對(duì)消息內(nèi)容不感興趣的節(jié)點(diǎn)或者消息本身保密性較強(qiáng)，則保證消息轉(zhuǎn)發(fā)以后的有效性和安全性。

具體sharing 路由算法偽碼如下:

3 實(shí)驗(yàn)與仿真

3.1 仿真場(chǎng)景設(shè)計(jì)

在本文中，使用ONE(Opportunistic Network Environment)仿真工具［15］，并且建立如圖2 的仿真場(chǎng)景模型，模擬在A，B，C，D 4 個(gè)社區(qū)的城鎮(zhèn)范圍內(nèi)，通過(guò)社區(qū)成員之間隨身短距離通訊設(shè)施組成的移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)共享資源。其中每個(gè)社區(qū)地理范圍之內(nèi)為該社區(qū)的錨區(qū)，而以社區(qū)消息的目的簇節(jié)點(diǎn)集合為該社區(qū)的社員。具體網(wǎng)絡(luò)參數(shù)如表1 所示。

圖2 仿真場(chǎng)景模型圖

表1 仿真場(chǎng)景參數(shù)設(shè)置

3.2 評(píng)價(jià)指標(biāo)

結(jié)合機(jī)會(huì)網(wǎng)絡(luò)性能評(píng)價(jià)指標(biāo)和本文中消息共享網(wǎng)絡(luò)的特點(diǎn)，擬采用以下參數(shù)評(píng)價(jià)網(wǎng)絡(luò)的性能。

1)社區(qū)消息遞交率。

指當(dāng)前社區(qū)中所有消息在社區(qū)范圍內(nèi)的分享普及率，計(jì)算公式如下:

其中，Nm表示當(dāng)前社區(qū)消息總數(shù)量，Di表示已成功接收消息mi的社區(qū)節(jié)點(diǎn)個(gè)數(shù)，Nc表示社區(qū)節(jié)點(diǎn)的總個(gè)數(shù)。

2)平均時(shí)延。

指當(dāng)前網(wǎng)絡(luò)中節(jié)點(diǎn)收到消息所需要的網(wǎng)絡(luò)延時(shí)的平均值，計(jì)算公式如下:

其中，Rm表示成功接收消息m 的節(jié)點(diǎn)個(gè)數(shù)，tij表示節(jié)點(diǎn)j 收到消息mi的時(shí)延，Nm表示消息總數(shù)量。

3)平均權(quán)重。

指當(dāng)前網(wǎng)絡(luò)中目的節(jié)點(diǎn)成功接收消息時(shí)的消息的平均權(quán)重的平均值，計(jì)算公式如下:

其中，Wij表示節(jié)點(diǎn)N 收到消息mi時(shí)消息的及時(shí)權(quán)重。

4)網(wǎng)絡(luò)負(fù)載。

指網(wǎng)絡(luò)中中繼轉(zhuǎn)發(fā)消息次數(shù)與成功遞交消息次數(shù)的比值，計(jì)算公式如下:

其中，F(xiàn)i表示消息mi在網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)次數(shù)。

3.3 實(shí)驗(yàn)分析

在3.1 節(jié)建立的實(shí)驗(yàn)場(chǎng)景中，分別仿真利用epidemic 路由算法、采用weight 優(yōu)先調(diào)度策略的epdemic-W 路由算法、本文提出的資源分享sharing 路由算法在網(wǎng)絡(luò)中傳輸社區(qū)共享消息，實(shí)驗(yàn)結(jié)果如圖3～圖6 所示。

從圖3 可以看出，隨著網(wǎng)絡(luò)仿真時(shí)間的增長(zhǎng)，使用3 種路由算法的A，B，C，D 4 個(gè)社區(qū)網(wǎng)絡(luò)中的消息傳遞率都在上升，其中可以明顯地看出sharing 路由算法傳遞率最高，epidemic 算法傳遞率最低，這是由于sharing 算法充分考慮了社區(qū)消息的錨區(qū)和消息目的簇節(jié)點(diǎn)而進(jìn)行有目的性的轉(zhuǎn)發(fā)，所以網(wǎng)絡(luò)中的效率大大地提升。而epidemic-W 算法中，由于weight 優(yōu)先調(diào)度算法優(yōu)先調(diào)用生命周期長(zhǎng)的消息，使得消息可以有效地繼續(xù)在網(wǎng)絡(luò)中傳播。最后還可以看出，處于交通樞紐的社區(qū)B 中使用sharing 算法的傳遞率明顯地高于其他3 個(gè)社區(qū)，而使用其他2 種路由算法均低于其他3 個(gè)社區(qū)，這正是因?yàn)閟haring 路由算法中錨區(qū)的作用，保證消息在社區(qū)外傳輸時(shí)只會(huì)向目的節(jié)點(diǎn)傳輸，而后2 種路由算法中消息會(huì)在網(wǎng)絡(luò)中無(wú)目的性的隨意蔓延。

圖3 消息傳遞率

圖4 消息平均時(shí)延

圖5 消息平均權(quán)重

圖6 網(wǎng)絡(luò)平均負(fù)載

從圖4 中可以看出，使用sharing 路由算法的網(wǎng)絡(luò)中，消息傳遞時(shí)延比其他2 種路由算法明顯地降低，越短的消息時(shí)延意味著消息能更快地傳輸?shù)缴鐓^(qū)中的每個(gè)節(jié)點(diǎn)，尤其是在人員更為混雜的社區(qū)B 中，充分說(shuō)明了sharing 路由算法的高效性。

從圖5 中可以看出，有wight 調(diào)度機(jī)制的sharing路由算法和epidemic-W 路由算法下的網(wǎng)絡(luò)中消息的平均權(quán)重明顯優(yōu)于無(wú)wight 調(diào)度機(jī)制的epidemic 路由算法的網(wǎng)絡(luò)。充分說(shuō)明了weight 調(diào)度算法的正確性和高效性，在社區(qū)網(wǎng)絡(luò)中，優(yōu)先級(jí)別更高的緊急信息能夠更快速地到達(dá)更多的目的節(jié)點(diǎn)，保證了消息的及時(shí)和有效。

從圖6 中可以發(fā)現(xiàn)4 個(gè)社區(qū)網(wǎng)絡(luò)場(chǎng)景中，sharing路由算法的網(wǎng)絡(luò)負(fù)載大大低于其他2 種路由算法，因?yàn)閟haring 路由算法中的消息錨區(qū)策略和消息簇節(jié)點(diǎn)的策略保證了路由算法傳輸時(shí)的有效性，使消息對(duì)目的節(jié)點(diǎn)轉(zhuǎn)發(fā)的概率大大增加。越低的網(wǎng)絡(luò)負(fù)載表明網(wǎng)絡(luò)中能量等消耗越少，網(wǎng)絡(luò)的效率也會(huì)更高。

綜上實(shí)驗(yàn)，驗(yàn)證了基于weight 調(diào)度算法的有效性，在此調(diào)度策略的路由算法的網(wǎng)絡(luò)中傳遞消息的權(quán)重明顯增高;驗(yàn)證了sharing 路由算法在社區(qū)信息共享網(wǎng)絡(luò)中的高效性，其網(wǎng)絡(luò)的消息傳遞率、時(shí)延、網(wǎng)絡(luò)負(fù)載都明顯優(yōu)于其他算法。

4 結(jié)束語(yǔ)

本文根據(jù)資源共享機(jī)會(huì)網(wǎng)絡(luò)的特征，提出消息目的簇及消息錨區(qū)的概念，并且結(jié)合消息的優(yōu)先級(jí)，提出基于消息權(quán)重的調(diào)度算法和資源共享機(jī)會(huì)網(wǎng)絡(luò)的sharing 路由算法。通過(guò)該路由算法可以根據(jù)消息的屬性，更快速和廣泛地在網(wǎng)絡(luò)中傳輸共享消息。通過(guò)實(shí)驗(yàn)證實(shí)了sharing 路由算法總體的網(wǎng)絡(luò)性能均高于現(xiàn)有傳輸速度最快的epidemic 等算法。

［1］Pirozmand P，Wu G，Jedari B，et al.Human mobility in opportunistic networks:Characteristics，models and prediction methods［J］.Journal of Network and Computer Applications，2014，42:45-58.

［2］Biagioni E，Giordano S.Ad Hoc and sensor networks［Series Editorial］［J］.IEEE Communications Magazine，2015，53(1):248.

［3］Lin Yaguang，Wang Xiaoming，Zhang Lichen，et al.The impact of node velocity diversity on mobile opportunistic network performance［J］.Journal of Network and Computer Applications，2015，55:47-58.

［4］Pan Daru，Zhang Hui，Chen Weijing，et al.Transmission of multimedia contents in opportunistic networks with social selfish nodes［J］.Multimedia Systems，2015，21(3):277-288.

［5］Martin-Campillo A，Crowcroft J，Yoneki E，et al.Evaluating opportunistic networks in disaster scenarios［J］.Journal of Network and Computer Applications，2013，36(2):870-880.

［6］Punceva M，Rodero I，Parashar M，et al.Incentivising resource sharing in social clouds［J］.Concurrency and Computation:Practice and Experience，2015，27(6):1483-1497.

［7］Helmle S，Kuhn M，Pesch D，et al.Multi-hop link adaptation for emergency services narrowband mobile ad-hoc networks［C］// Proceedings of the 10th International ITG Conference on Systems，Communications and Coding.2015:1-6.

［8］Fujihara A，Miwa H.Disaster evacuation guidance using opportunistic communication:The potential for opportunitybased service［J］.Studies in Computational Intelligence，2014，546:425-446.

［9］Yuan Peiyan，Tang Shaojie.Community-based immunization in opportunistic social networks［J］.Physica A:Statistical Mechanics and its Applications，2015，420:85-97.

［10］Ciobanu R，Marin R，Dobre C，et al.Interest-awareness in data dissemination for opportunistic networks［J］.Ad Hoc Networks，2015，25:330-345.

［11］Wu Honghai，Ma Huadong，Zhao Dong.Videocent:A quality-oriented incentive mechanism for video delivery in opportunistic networks［J］.Wireless Networks，2015，21(3):769-781.

［12］Zhang X，Neglia G，Kurose J，et al.Performance modeling of epidemic routing［J］.Computer Networks，2007，51(10):2867-2891.

［13］Zhang Sheng，Qian Zhuzhong，Wu Jie，et al.Virtual network embedding with opportunistic resource sharing［J］.IEEE Transactions on Parallel ＆ Distributed Systems，2014，25(3):816-827.

［14］Mohan S，Qu G，Mili F.Lecture Notes in Computer Science［M］.Springer Berlin Heidelberg，2012:462-478.

［15］Wang Zhen，Wang Xinhua，Sui Jingqi.Extending research for ONE simulator of opportunistic network［J］.Application Research of Computers，2012，29(1):272-277.