黃成兵

（阿壩師范學(xué)院計(jì)算機(jī)科學(xué)系 汶川 623002）

1 引言

移動互聯(lián)網(wǎng)的發(fā)展和技術(shù)的進(jìn)步，使得大量智能手持通信設(shè)備不斷更新，也使得人們對通信質(zhì)量和多樣性的需求不斷提升。從PC機(jī)誕生到可隨身攜帶的移動終端設(shè)備，無不體現(xiàn)人們對通訊設(shè)備的迷戀和追求。通信設(shè)備的發(fā)展離不開基礎(chǔ)通訊網(wǎng)絡(luò)的發(fā)展和架構(gòu)。撫今追昔，我們不難發(fā)現(xiàn)從開始發(fā)展到現(xiàn)在還在沿用的端到端網(wǎng)絡(luò)至今天可無需依靠基礎(chǔ)設(shè)施而自行構(gòu)建的自組織網(wǎng)絡(luò)，都是通信設(shè)備得以生存發(fā)展的前提條件。隨著時代的變遷，人民生活水平的提高，傳統(tǒng)網(wǎng)絡(luò)已不能滿足人們在特殊情況下的一些特殊需求，急需一種新的網(wǎng)絡(luò)結(jié)構(gòu)來彌補(bǔ)這些空缺。

機(jī)會網(wǎng)絡(luò)［1］因?yàn)槠涔?jié)點(diǎn)的移動特性和稀疏特性，導(dǎo)致當(dāng)節(jié)點(diǎn)射頻關(guān)閉或者節(jié)點(diǎn)發(fā)射信號遇到障礙物時造成信號衰減會引起網(wǎng)絡(luò)在多數(shù)時間內(nèi)不能連通。因此，在這樣復(fù)雜且多變的網(wǎng)絡(luò)環(huán)境中，傳統(tǒng)的無線自組織網(wǎng)絡(luò)通信模式將不能有效運(yùn)行。因?yàn)閭鹘y(tǒng)的自組織網(wǎng)絡(luò)在數(shù)據(jù)轉(zhuǎn)發(fā)之前，都需通過某種路由算法建立可通信鏈路，這些路由算法［2］包括：AODV（ad-hoc on-demand distance vec?tor），DSR（dynamic source routing），且信息轉(zhuǎn)發(fā)到哪一個目標(biāo)節(jié)點(diǎn)也將根據(jù)預(yù)先設(shè)計(jì)好的路由表進(jìn)行選擇。無線自組織網(wǎng)絡(luò)的這一通信模式包含的一個重要假設(shè)是網(wǎng)絡(luò)在大部分時間內(nèi)是互聯(lián)的，網(wǎng)絡(luò)中任意兩個節(jié)點(diǎn)之間都存在一條或多條通信鏈路。但在機(jī)會網(wǎng)絡(luò)中，網(wǎng)絡(luò)可能在某個特定時間段內(nèi)會被分割成為互不連通的多個子區(qū)域，這就導(dǎo)致了源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間由于不在一個連通區(qū)域內(nèi)而不能實(shí)現(xiàn)直接通信。因此，機(jī)會網(wǎng)絡(luò)中最大的挑戰(zhàn)就是如何設(shè)計(jì)出一種應(yīng)對這種復(fù)雜多變的網(wǎng)絡(luò)路由算法。

在現(xiàn)實(shí)生活中由于人的活動都具有某些特定的規(guī)律，如每個人每天都會上班下班上學(xué)放學(xué)等，且這些人都會在某一個特定的區(qū)域內(nèi)活動頻繁，而在其他區(qū)域活動則相對較弱。因此有學(xué)者提出利用人活動的這一特性完成信息的傳輸，降低通信成本［3］。

2 相關(guān)工作

網(wǎng)絡(luò)通信傳輸?shù)母締栴}是路由問題。由于機(jī)會網(wǎng)絡(luò)鏈路間斷特性，通信過程中往往出現(xiàn)源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間不存在完整的通信鏈路從而需要不斷尋找中間節(jié)點(diǎn)以建立傳輸鏈路。機(jī)會網(wǎng)絡(luò)中的路由問題本質(zhì)就是選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的決策問題，這與根據(jù)網(wǎng)絡(luò)狀態(tài)進(jìn)行建立和維護(hù)路由的傳統(tǒng)互聯(lián)網(wǎng)絡(luò)通信不同。研究人員利用節(jié)點(diǎn)移動這一特性提出了多種路由算法，如Epdemic［4］，PROPHET［5］，Spray and Wait［6］等算法。這些算法的核心思想都是基于將同一消息的多份副本放入網(wǎng)絡(luò)中，若一個副本到達(dá)目的節(jié)點(diǎn)，那么這個消息傳遞成功。通過適當(dāng)增加網(wǎng)絡(luò)中消息副本的數(shù)量能提高消息的傳輸?shù)某晒β屎徒档蛡鬏斞舆t，但是消息副本數(shù)量過多又會造成節(jié)點(diǎn)會緩存溢出，使得節(jié)點(diǎn)能量過度消耗。因而有效地管理和控制消息副本數(shù)量對于提高消息傳輸成功率顯得尤為重要。

BUBBLE算法［7］是由Pan Hui等提出的一種基于社區(qū)并適用于DTN網(wǎng)絡(luò)的單拷貝路由算法，該算法以現(xiàn)實(shí)生活中真實(shí)移動軌跡為節(jié)點(diǎn)移動模型。首先計(jì)算出每個節(jié)點(diǎn)的活躍度，然后根據(jù)活躍度的大小選擇進(jìn)行消息轉(zhuǎn)發(fā)的中繼節(jié)點(diǎn)。該算法在網(wǎng)絡(luò)系統(tǒng)和社區(qū)內(nèi)依據(jù)活躍度進(jìn)行排名并設(shè)計(jì)全局和社區(qū)排序表。消息進(jìn)行傳輸?shù)穆酚刹呗允鞘紫扔稍垂?jié)點(diǎn)將消息轉(zhuǎn)發(fā)給全局中活躍度比自己大的節(jié)點(diǎn)，當(dāng)消息被轉(zhuǎn)發(fā)到與目的節(jié)點(diǎn)同屬一個社區(qū)的中繼節(jié)點(diǎn)時，中繼節(jié)點(diǎn)根據(jù)社區(qū)活躍度排序表大小排名進(jìn)行消息轉(zhuǎn)發(fā)，直到消息到達(dá)目的節(jié)點(diǎn)為止。該算法充分利用人們之間的社會關(guān)系帶來的通信機(jī)會進(jìn)行消息轉(zhuǎn)發(fā)，充分利用了活躍度高的節(jié)點(diǎn)與活躍度低的節(jié)點(diǎn)有較多的相遇機(jī)會這一特性。該算法是單拷貝策略，所以在有效控制網(wǎng)絡(luò)中消息副本數(shù)目的同時，也增大了消息的傳輸延遲。

針對社區(qū)機(jī)會網(wǎng)絡(luò)特性，本文提出一種基于Epdemic的改進(jìn)算法。該算法首先計(jì)算在網(wǎng)絡(luò)釋放的信息副本數(shù)目，然后對節(jié)點(diǎn)緩存的副本進(jìn)行管理，使得信息都不會因?yàn)榫彺嬉绯龆粊G棄。

3 基于Epdemic算法的消息緩存管理

3.1 社區(qū)機(jī)會網(wǎng)絡(luò)移動模型的創(chuàng)建

多數(shù)的節(jié)點(diǎn)移動模型都基于以下兩個假設(shè)：1）網(wǎng)絡(luò)中的每個節(jié)點(diǎn)都能等概率的移動到任意位置；2）所有節(jié)點(diǎn)都具有相同的移動特性。但對基于事實(shí)的網(wǎng)絡(luò)移動軌跡的大量研究證明，這兩個假設(shè)在現(xiàn)實(shí)情況下是很難成立的［8］。為了使在仿真中具有社區(qū)特點(diǎn)的節(jié)點(diǎn)移動更接近真實(shí)，本文提出一個基于社區(qū)的節(jié)點(diǎn)移動模型［9］，該模型中節(jié)點(diǎn)的移動分為兩個階段：1）本地社區(qū)階段；2）漫游階段。兩個階段在節(jié)點(diǎn)移動的時候不斷交替進(jìn)行。該模型具體描述如下：

每個節(jié)點(diǎn)都隸屬于一個本地社區(qū)Cl，節(jié)點(diǎn)在社區(qū)內(nèi)采用經(jīng)典的移動模型為Random Waypoint。

本地社區(qū)階段（Local Community Epoch）：節(jié)點(diǎn)被限制在本地社區(qū)Cl內(nèi)運(yùn)動，其運(yùn)動的時間長度為-Lr，節(jié)點(diǎn)此時所處的狀態(tài)稱為本地狀態(tài)Sl。

漫游階段（Roaming Epoch）：節(jié)點(diǎn)大部分時間在所屬社區(qū)Cl內(nèi)運(yùn)動，有時可移動到其他社區(qū)，節(jié)點(diǎn)在Cl外運(yùn)動時間預(yù)期為-Ll，節(jié)點(diǎn)此時所處的狀態(tài)稱為漫游狀態(tài)Sr。

節(jié)點(diǎn)的移動形成了一個由本地社區(qū)階段和漫游階段組成的序列。

本地社區(qū)概率（Local Community Probability）：如果前一個階段節(jié)點(diǎn)處于本地社區(qū)狀態(tài)為Sl，則下一個階段節(jié)點(diǎn)處于本地社區(qū)狀態(tài)仍為Sl的概率為pl，處于漫游狀態(tài)的概率為1-pl。

漫游概率（Local Community Probability）：如果前一個階段節(jié)點(diǎn)處于漫游階段，狀態(tài)為漫游狀態(tài)Sr，則下一個階段節(jié)點(diǎn)仍處于漫游狀態(tài)的概率為pr，處于本地社區(qū)進(jìn)行移動的概率為1-pr。

此模型依據(jù)觀察現(xiàn)實(shí)生活中各種真實(shí)的節(jié)點(diǎn)移動軌跡的移動特性，將上述具有社區(qū)特點(diǎn)的節(jié)點(diǎn)移動模型表述為兩個狀態(tài)的馬爾科夫鏈，如圖1所示。

據(jù)上述節(jié)點(diǎn)狀態(tài)變化的馬爾科夫鏈圖，由馬爾科夫鏈理論可得：

在任一給定階段，節(jié)點(diǎn)處于本地狀態(tài)的概率為

在任一給定階段，節(jié)點(diǎn)處于漫游狀態(tài)的概率為

以上述模型運(yùn)行的節(jié)點(diǎn)往往具有本地特征，即他們的大部門時間都是在本地社區(qū)內(nèi)，概率pl＞60%；有時節(jié)點(diǎn)也會離開本地社區(qū)到其它地區(qū)漫游，漫游的概率為pr。不同的節(jié)點(diǎn)可以有不同的參數(shù)值（pl，pr），這正符合節(jié)點(diǎn)在大范圍內(nèi)移動的特征變化模型。

圖1 節(jié)點(diǎn)狀態(tài)變化圖

3.2 控制消息副本數(shù)量

使用Epdemic路由算法進(jìn)行社區(qū)間消息傳遞的時候，將導(dǎo)致某一社區(qū)內(nèi)消息副本數(shù)目過多，從而使得大量節(jié)點(diǎn)的緩存飽和。當(dāng)節(jié)點(diǎn)接收到新的消息的時候，不得不將舊的消息丟棄，然而舊的消息可能還沒有傳輸成功，這樣就導(dǎo)致了Epdemic路由算法的性能下降。因此，合理控制網(wǎng)絡(luò)中消息副本數(shù)目將有效改善消息的投遞率。

論文［10］中已經(jīng)提出在Random-Waypoint下，節(jié)點(diǎn)平均移動的相遇時間是EMrwp，計(jì)算公式如下：

在式（3）中，Tˉ為節(jié)點(diǎn)的平均移動時間，----Tstop為節(jié)點(diǎn)的平均暫停時間任意一個時刻的移動概率，vrwp是 Random-Way?point移動模型中節(jié)點(diǎn)的歸一化速度，N表示節(jié)點(diǎn)的移動范圍，K為節(jié)點(diǎn)的通信范圍，Lˉ為節(jié)點(diǎn)一次移動的平均距離，在 N× N的正方形區(qū)域中Lˉ=0.5214 N 。節(jié)點(diǎn)在以Random-Waypoint模型移動時，每隔EMrwp時段就會有兩個節(jié)點(diǎn)相遇，EMrwp值的大小決定了節(jié)點(diǎn)相遇是否頻繁。

當(dāng)假設(shè)節(jié)點(diǎn)能量不被完全消耗的情況下，Ep?demic路由算法的傳輸延遲在性能上接近理論最優(yōu)值EMopt，計(jì)算公式如下：

式中C為常數(shù)，可取0.34，N為節(jié)點(diǎn)的移動范圍，M為節(jié)點(diǎn)數(shù)量，V?為節(jié)點(diǎn)的平均移動速度，K為節(jié)點(diǎn)的通信范圍，網(wǎng)絡(luò)中每個節(jié)點(diǎn)按最優(yōu)路徑到達(dá)目的節(jié)點(diǎn)的轉(zhuǎn)發(fā)次數(shù)為D可用下式計(jì)算：

確定了轉(zhuǎn)發(fā)次數(shù)就可以確定網(wǎng)絡(luò)中每個數(shù)據(jù)副本總數(shù)為D。

3.3 管理緩存溢出

在節(jié)點(diǎn)內(nèi)緩存空間是有限的，要想在有限的空間內(nèi)接收新的信息，同時又要使舊的信息不因空間有限被刪除，就要對當(dāng)緩存發(fā)生溢出時采取合理的刪除手段進(jìn)行管理［11］。為此本文引入了一種具有退避機(jī)制的緩存管理辦法。具體如下：

1）網(wǎng)絡(luò)中每個節(jié)點(diǎn)維護(hù)一個字段，該字段用來存放閾值t。

2）閾值t是隨機(jī)產(chǎn)生的，并且服從均勻分布，其值范圍是（0，x）。其中x是參數(shù)，取值根據(jù)網(wǎng)絡(luò)狀況而定。

3）當(dāng)某一通信節(jié)點(diǎn)緩存充滿后，在時間t內(nèi)，該節(jié)點(diǎn)將拒絕接收目標(biāo)節(jié)點(diǎn)的數(shù)據(jù)分組，即在閾值時刻內(nèi)令其他節(jié)點(diǎn)的數(shù)據(jù)分組退避。

4）當(dāng)退避時間超過t后，無論節(jié)點(diǎn)緩存狀態(tài)如何均接收數(shù)據(jù)分組，此時可能還會發(fā)生擠出事件。接收數(shù)據(jù)分組后，將退避時間設(shè)為零。

通過上述策略可以減小緩存溢出的頻繁發(fā)生，尤其是路由采用洪泛算法情況下。

4 仿真和結(jié)果分析

4.1 仿真環(huán)境設(shè)置

本文采用仿真器ONE［12］對算法性能進(jìn)行仿真，將其仿真結(jié)果和Epdemic算法、SA-Epdemic算法進(jìn)行比較。由于本算法在網(wǎng)絡(luò)運(yùn)行初期要計(jì)算Pi值，所以仿真開始時先進(jìn)行1000s的預(yù)熱。社區(qū)布局為4*4的方式，在所有節(jié)點(diǎn)之間隨機(jī)分布網(wǎng)絡(luò)節(jié)點(diǎn)。為了使節(jié)點(diǎn)的移動模型更加接近于真實(shí)情況，本文參照SF［13］算法設(shè)置的仿真場景來模擬真實(shí)的網(wǎng)絡(luò)移動軌跡。將網(wǎng)絡(luò)中的節(jié)點(diǎn)分為兩類，一類稱為本地節(jié)點(diǎn)，數(shù)目占整個網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的80%，它們絕大部分時間在本地社區(qū)移動，其Pl在［0.8，0.95］之間取值，同時本地節(jié)點(diǎn)也會在網(wǎng)絡(luò)中的其它社區(qū)漫游，其Pr在［0.1，0.2］之間取值；另一類稱為漫游節(jié)點(diǎn)，數(shù)目占網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)的20%，此類節(jié)點(diǎn)經(jīng)常在網(wǎng)絡(luò)中其他社區(qū)漫游，其Pr的值分布在［0.3，0.4］之間，漫游節(jié)點(diǎn)大部分時間仍在本地社區(qū)內(nèi)移動，其Pl在［0.7，0.8］之間取值。其它的主要仿真參數(shù)如表1所示。

表1 主要的仿真參數(shù)

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

4.2.1 消息數(shù)量和傳輸成功率的關(guān)系

由圖2可以看出，隨著消息數(shù)量的不斷增多，使用Epdemic算法進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，消息的傳輸成功率下降的速度要快于B-Epdemic算法。B-Epdemic并沒有對路由路由算法Epdemic本身做修改，而是根據(jù)節(jié)點(diǎn)的社區(qū)特性對消息進(jìn)行一個有效的管理，從而提高了Epdemic算法在社區(qū)模型中消息的傳輸成功率。

圖2 消息數(shù)量和傳輸成功率的關(guān)系

4.2.2 消息數(shù)量和路由開銷的關(guān)系

由圖3可以看出隨著消息數(shù)量增多，路由開銷都在下降，但是Epdemic算法的路由開銷始終大于B-Epdemic，這不難解釋。因?yàn)镋pdemic算法是洪泛算法，不停的在傳播消息，而B-Epdemic有所限制。因此從仿真開始到結(jié)束，Epdemic算法的路由開銷一直大于B-Epdemic算法的開銷。

圖3 消息數(shù)量和路由開銷的關(guān)系

4.2.3 消息數(shù)量和傳輸延遲的關(guān)系

由圖4可以看出，隨著消息數(shù)量的不斷增多，兩種算法的傳輸延遲都是不斷增加，這是由于信息的增多，使得各個節(jié)點(diǎn)內(nèi)部沒有多余的存儲空間，只能等待消息過期被刪除才能接收新的消息。但B-Epdmeic算法的傳輸延遲明顯要大于Epdemic，因?yàn)楸旧鞡-Epdemic對消息數(shù)量進(jìn)行了限制，又有緩存溢出的管理，所以傳輸延遲會更大。

圖4 消息數(shù)量和傳輸延遲的關(guān)系

5 結(jié)語

文中首先分析了當(dāng)前機(jī)會網(wǎng)絡(luò)的發(fā)展現(xiàn)狀和幾種經(jīng)典路由算法，以及這些路由算法應(yīng)用在社區(qū)機(jī)會網(wǎng)絡(luò)中存在的相關(guān)問題。針對社區(qū)內(nèi)節(jié)點(diǎn)移動特點(diǎn)和不足，提出B-Epdemic算法。該算法基于社區(qū)機(jī)會網(wǎng)絡(luò)的消息緩存管理策略進(jìn)行優(yōu)化，能夠使傳輸消息在的社區(qū)機(jī)會網(wǎng)絡(luò)中以較高的傳輸成功率和較低的路由開銷進(jìn)行傳輸。實(shí)驗(yàn)結(jié)果表明B-Epdemic算法在較好的控制消息副本數(shù)量的同時減小了緩存溢出的發(fā)生。在允許較大延遲的情況下使得消息傳輸成功率、路由開銷相比原Ep?demic算法都有顯著提高。