吳大鵬，張普寧，王汝言

（重慶郵電大學(xué) 寬帶泛在接入技術(shù)研究所，重慶 400065）

1 引言

隨著各種智能設(shè)備的大量涌現(xiàn)，移動(dòng)自組織網(wǎng)絡(luò)（MANET, mobile ad hoc network）得到了快速的發(fā)展，內(nèi)置藍(lán)牙或Wi-Fi模塊的移動(dòng)終端可自組織成各種微型網(wǎng)絡(luò)，以實(shí)現(xiàn)數(shù)據(jù)共享和交互[1]，其應(yīng)用范圍包括交通狀況信息交互[2]、野生動(dòng)物監(jiān)控[3,4]、偏遠(yuǎn)地區(qū)無線網(wǎng)絡(luò)接入[5,6]等。但是，在移動(dòng)自組織網(wǎng)絡(luò)中，節(jié)點(diǎn)間轉(zhuǎn)發(fā)數(shù)據(jù)之前需建立端到端路徑[7]，由于網(wǎng)絡(luò)稀疏、節(jié)點(diǎn)快速移動(dòng)和通信范圍受限等因素，源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)間的路徑經(jīng)常出現(xiàn)斷裂，導(dǎo)致節(jié)點(diǎn)之間無法通信。為實(shí)現(xiàn)該種環(huán)境下的通信，充分利用節(jié)點(diǎn)移動(dòng)過程所帶來的相遇機(jī)會(huì)，研究人員提出了機(jī)會(huì)網(wǎng)絡(luò)體系結(jié)構(gòu)[8]。

機(jī)會(huì)網(wǎng)絡(luò)的概念部分繼承于延遲容忍網(wǎng)絡(luò)（DTN, delay tolerance network），其數(shù)據(jù)轉(zhuǎn)發(fā)形式與系統(tǒng)架構(gòu)具有延遲容忍網(wǎng)絡(luò)的一般化特征，但針對(duì)機(jī)會(huì)網(wǎng)絡(luò)的相關(guān)研究強(qiáng)化了對(duì)節(jié)點(diǎn)高速移動(dòng)、拓?fù)淇焖僮兓木W(wǎng)絡(luò)環(huán)境的適應(yīng)性，以滿足復(fù)雜動(dòng)態(tài)場(chǎng)景下的通信需求。機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)前不需建立端到端路徑，與MANET所采用的存儲(chǔ)—轉(zhuǎn)發(fā)通信模式不同，機(jī)會(huì)網(wǎng)絡(luò)采取更為靈活的存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)模式進(jìn)行通信。顯然，通信過程充分利用了節(jié)點(diǎn)隨機(jī)移動(dòng)帶來的相遇機(jī)會(huì)，有效地克服了端到端路徑失效所造成的通信中斷問題。但是，機(jī)會(huì)網(wǎng)絡(luò)在增加通信靈活性的同時(shí)，也為路由協(xié)議的設(shè)計(jì)帶來了巨大的挑戰(zhàn)。

目前，針對(duì)機(jī)會(huì)網(wǎng)絡(luò)的特點(diǎn)，國內(nèi)外的研究人員提出了多種路由機(jī)制。根據(jù)相同消息在網(wǎng)絡(luò)中的分布情況，可以將這些機(jī)制分為2類：多副本機(jī)制和單副本機(jī)制。文獻(xiàn)[9]指出多副本機(jī)制擁有較低的時(shí)延和較高的可靠性，但其占用了大量的網(wǎng)絡(luò)帶寬及緩存空間，消耗了節(jié)點(diǎn)大量能量，不適用于資源受限的機(jī)會(huì)網(wǎng)絡(luò)。文獻(xiàn)[10]對(duì)當(dāng)前的單副本機(jī)制進(jìn)行了深入研究，指出在節(jié)點(diǎn)能量及帶寬受限的情況下，單副本路由策略在網(wǎng)絡(luò)資源開銷方面具備較強(qiáng)的優(yōu)勢(shì)。然而，機(jī)會(huì)網(wǎng)絡(luò)中的鏈路具有間斷連接特性，單副本機(jī)制的設(shè)計(jì)需要考慮多種因素，以合理地選擇中繼節(jié)點(diǎn)，達(dá)到有效降低網(wǎng)絡(luò)資源開銷的目的。目前，單副本路由機(jī)制中比較具有代表性的是PROPHET機(jī)制[11]，其基本原理是根據(jù)節(jié)點(diǎn)運(yùn)動(dòng)過程歷史信息，利用概率傳遞性預(yù)測(cè)相遇狀態(tài)，進(jìn)而決定消息的轉(zhuǎn)發(fā)。但是，與其他類型的通信網(wǎng)絡(luò)路由協(xié)議研究類似，所提出的PROPHET機(jī)制采用靜態(tài)抽象圖建立網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路之間的關(guān)系[12]。對(duì)于機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)來說，隨機(jī)運(yùn)動(dòng)過程使得節(jié)點(diǎn)間的鏈路具有時(shí)變特性，傳統(tǒng)的靜態(tài)抽象圖無法準(zhǔn)確、及時(shí)地反映鏈路隨時(shí)間的變化情況，導(dǎo)致相關(guān)路由機(jī)制無法有效工作[13]。

本文提出了一種適用于機(jī)會(huì)網(wǎng)絡(luò)的消息轉(zhuǎn)發(fā)策略 CSAMT(connection status aware message transmission)，節(jié)點(diǎn)根據(jù)歷史態(tài)勢(shì)信息建立時(shí)序圖模型，描述與網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)之間的關(guān)系，并動(dòng)態(tài)地以多維方式感知節(jié)點(diǎn)間的連接態(tài)勢(shì)，其中，包括可達(dá)率、時(shí)延及跳數(shù)3個(gè)方面因素，利用所提出的均衡方法，經(jīng)過非均勻量化，進(jìn)而以分布式的方式對(duì)消息轉(zhuǎn)發(fā)進(jìn)行決策。

2 時(shí)序圖模型

傳統(tǒng)靜態(tài)圖方法將節(jié)點(diǎn)間非同時(shí)出現(xiàn)的鏈路聚合為非時(shí)變的連接圖。然而，網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)改變是機(jī)會(huì)網(wǎng)絡(luò)的內(nèi)在屬性，這種靜態(tài)或聚合的分析方法忽略了節(jié)點(diǎn)間連接出現(xiàn)的時(shí)間順序，使得節(jié)點(diǎn)間可用的通信路徑被嚴(yán)重高估。時(shí)序圖模型將傳統(tǒng)的非時(shí)變靜態(tài)圖以時(shí)間順序劃分為一系列有限的離散時(shí)間序列圖，以反映機(jī)會(huì)網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)演進(jìn)過程和趨勢(shì)，進(jìn)而，感知節(jié)點(diǎn)的運(yùn)動(dòng)規(guī)律及連接態(tài)勢(shì)。

采用靜態(tài)圖方法將節(jié)點(diǎn)運(yùn)動(dòng)過程進(jìn)行抽象的結(jié)果如圖1(a)所示，隨機(jī)運(yùn)動(dòng)的節(jié)點(diǎn)作為圖1(a)中的頂點(diǎn)，節(jié)點(diǎn)之間的相遇過程則抽象為邊，其中，ei表示節(jié)點(diǎn)之間通過隨機(jī)運(yùn)動(dòng)過程產(chǎn)生連接。

時(shí)序圖模型可將上述多個(gè)節(jié)點(diǎn)之間的運(yùn)動(dòng)過程表示為 G = ＜ V ( G), E( G ), φ(G)＞ ，其中， V ( G)={A, B, C, D, E}，E ( G ) = {e1, e2, e3, e4, e5, e6, e7}，φ(G):E→V×V，如圖1（b）所示，可知，圖G為無向簡單圖。圖 GTi=＜ V ( GTi),E( GTi),φ(GTi)＞ 為 Ti時(shí)刻的時(shí)間序列圖，其中， V ( GTi) ? V( G), E( GTi)?E( G)，φ(GTi):E( GTi) → V ( GTi)× V ( GTi)，且圖 GTi為G的真子圖。連接序列圖中對(duì)應(yīng)節(jié)點(diǎn)間的虛線為時(shí)間演進(jìn)邊，其權(quán)值如式（1）所示，表示為節(jié)點(diǎn)的相遇間隔時(shí)間。

圖1 時(shí)序圖轉(zhuǎn)化過程

圖1(a)中存在節(jié)點(diǎn)A經(jīng)邊e3、e6投遞消息到達(dá)節(jié)點(diǎn)B的路徑，而由圖1(b)可知，邊e6先于e3出現(xiàn)，此時(shí)A尚未與節(jié)點(diǎn)D相遇，進(jìn)而，節(jié)點(diǎn)B就無法通過節(jié)點(diǎn)D收到來自于節(jié)點(diǎn)A的消息。顯然，靜態(tài)抽象圖方法忽略了節(jié)點(diǎn)相遇間隔、相遇頻率及連接出現(xiàn)的先后順序，視節(jié)點(diǎn)間的連接為同時(shí)存在，過高地估計(jì)了節(jié)點(diǎn)間存在的通信鏈路。圖1(b)所示的時(shí)序圖保存了節(jié)點(diǎn)相遇時(shí)間間隔、相遇頻率及連接次序等信息，忽略實(shí)際中并不存在的通信路徑，為準(zhǔn)確分析節(jié)點(diǎn)間連接態(tài)勢(shì)提供了依據(jù)。

機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)相遇狀態(tài)在時(shí)間域內(nèi)連續(xù)可變，為了便于分析，可將其抽象為離散化狀態(tài)，每個(gè)節(jié)點(diǎn)在本地緩存內(nèi)保存相遇信息列表，如表1所示，其中包含相遇節(jié)點(diǎn)的ID號(hào)及相遇時(shí)間。

表1 相遇信息

與機(jī)會(huì)網(wǎng)絡(luò)中的消息轉(zhuǎn)發(fā)原理類似，當(dāng)隨機(jī)運(yùn)動(dòng)的節(jié)點(diǎn)相遇之后，交換彼此緩存內(nèi)的相遇信息列表，該列表相對(duì)消息較小，其傳輸開銷可忽略不計(jì)。網(wǎng)絡(luò)狀態(tài)在有限的時(shí)間尺度內(nèi)趨于穩(wěn)定，通過不斷地交換相關(guān)信息，節(jié)點(diǎn)能夠近似地獲知全網(wǎng)的節(jié)點(diǎn)相遇狀態(tài)，進(jìn)而，以獲得的相遇時(shí)間順序?yàn)檩S線即可得到網(wǎng)絡(luò)連接態(tài)勢(shì)時(shí)序。其建立過程分為2個(gè)步驟進(jìn)行。1）狀態(tài)點(diǎn)創(chuàng)建。在每個(gè)相遇時(shí)刻，為網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)創(chuàng)建相應(yīng)的狀態(tài)點(diǎn)。如節(jié)點(diǎn)A發(fā)生了3次相遇事件，則在時(shí)序圖中分別在1T、2T、7T時(shí)刻建立A1, A2, A73個(gè)狀態(tài)點(diǎn)；2）建立關(guān)聯(lián)。以沿時(shí)間順序的有向虛線連接相同節(jié)點(diǎn)的不同狀態(tài)點(diǎn)，每一條虛線的權(quán)值為前后相遇時(shí)刻的差值，代表2個(gè)狀態(tài)點(diǎn)之間的時(shí)間距離，再以無權(quán)重的無向?qū)嵕€連接當(dāng)前時(shí)刻相遇的兩節(jié)點(diǎn)的狀態(tài)點(diǎn)，即可建立不同狀態(tài)點(diǎn)之間的關(guān)聯(lián)。

3 網(wǎng)絡(luò)狀態(tài)感知方法

對(duì)于采用存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)消息傳輸方式的機(jī)會(huì)網(wǎng)絡(luò)來說，節(jié)點(diǎn)隨機(jī)運(yùn)動(dòng)使得網(wǎng)絡(luò)狀態(tài)具有時(shí)變特性，中繼節(jié)點(diǎn)的選擇至關(guān)重要，需要考慮當(dāng)前網(wǎng)絡(luò)狀態(tài)。通常，節(jié)點(diǎn)間的相遇間隔時(shí)間、網(wǎng)絡(luò)負(fù)載率以及可達(dá)率為典型的網(wǎng)絡(luò)狀態(tài)表征參數(shù)，中繼節(jié)點(diǎn)選擇過程中需要對(duì)三者進(jìn)行綜合考慮。

根據(jù)時(shí)序圖iTG 中相關(guān)信息，由時(shí)間演進(jìn)邊eTe[V( GTi)]的對(duì)應(yīng)權(quán)值，可獲知任意節(jié)點(diǎn)之間的相遇間隔時(shí)間估計(jì)值 P ( i, j)，如式（2）所示。

其中，p ( i, j, Ti, null)表示給定時(shí)刻 Ti，節(jié)點(diǎn)i在 Ti后任意時(shí)刻與節(jié)點(diǎn)j的最短相遇間隔時(shí)間。節(jié)點(diǎn)隨機(jī)移動(dòng)使得節(jié)點(diǎn)之間在不同時(shí)刻可能多次相遇，本文選取各次相遇間隔時(shí)間的均值用于相遇間隔時(shí)間估計(jì)過程。

其次，網(wǎng)絡(luò)負(fù)載率反映了成功投遞消息所需的轉(zhuǎn)發(fā)次數(shù)，其定義如式（3）所示，其中，γ為網(wǎng)絡(luò)負(fù)載率，delN 為轉(zhuǎn)發(fā)的消息總數(shù)，sn為成功投遞到目標(biāo)節(jié)點(diǎn)的消息數(shù)?？梢姡D(zhuǎn)發(fā)次數(shù)越多，則網(wǎng)絡(luò)負(fù)載率越大。

根據(jù)時(shí)序圖 GTi中的相關(guān)信息，采用最短路徑算法可獲知任意節(jié)點(diǎn)間投遞消息所需的跳數(shù)G( i, j)，如式（4）所示。

其中， g ( i, j, Ti, null)為給定Ti時(shí)刻，節(jié)點(diǎn)i在Ti后任意時(shí)刻投遞消息到達(dá)節(jié)點(diǎn)j所需的最小跳數(shù)。通過比較消息到達(dá)目標(biāo)節(jié)點(diǎn)所需的平均跳數(shù)，選擇所需跳數(shù)較少的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)進(jìn)行消息轉(zhuǎn)發(fā)，能夠有效減少網(wǎng)絡(luò)負(fù)載。

網(wǎng)絡(luò)中任意節(jié)點(diǎn)間可能存在多條潛在通信鏈路，源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)間存在的潛在通信路徑越多，則消息被成功投遞的概率越高。因此，網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)間的相對(duì)可達(dá)率 V ( i, j)如式（5）所示。

其中， (,)V i j表示在節(jié)點(diǎn)i的n次相遇中存在從節(jié)點(diǎn)i到節(jié)點(diǎn)j的路徑的概率。顯然，若節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的V值越大，消息由該節(jié)點(diǎn)轉(zhuǎn)發(fā)到達(dá)目標(biāo)節(jié)點(diǎn)的成功率越高。

4 消息傳輸策略

根據(jù)動(dòng)態(tài)時(shí)序圖模型及所感知的相關(guān)網(wǎng)絡(luò)狀態(tài)，本部分對(duì)節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的能力進(jìn)行分析，并綜合考慮多個(gè)因素對(duì)消息轉(zhuǎn)發(fā)過程的影響，然后利用非均勻量化方法獲得轉(zhuǎn)發(fā)消息的相對(duì)能力，進(jìn)而更加合理地選擇中繼節(jié)點(diǎn)，完成對(duì)消息轉(zhuǎn)發(fā)。

4.1 節(jié)點(diǎn)轉(zhuǎn)發(fā)消息能力分析

根據(jù)建立的時(shí)序圖模型，節(jié)點(diǎn)能夠利用保存的歷史信息，估計(jì)消息到達(dá)網(wǎng)絡(luò)中任意節(jié)點(diǎn)的期望時(shí)延、平均跳數(shù)及相對(duì)可達(dá)率。然而，機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)隨機(jī)移動(dòng)，本地監(jiān)測(cè)結(jié)果無法準(zhǔn)確反應(yīng)網(wǎng)絡(luò)中其他節(jié)點(diǎn)狀態(tài)，需要以分布式的方式感知整個(gè)網(wǎng)絡(luò)范圍內(nèi)節(jié)點(diǎn)間的連接態(tài)勢(shì)，進(jìn)而預(yù)測(cè)節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的能力。

機(jī)會(huì)網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)獨(dú)立地進(jìn)行隨機(jī)運(yùn)動(dòng)，節(jié)點(diǎn)相遇之后彼此交換本地時(shí)序圖相關(guān)信息，隨著運(yùn)動(dòng)過程的持續(xù)，節(jié)點(diǎn)能夠獲知網(wǎng)內(nèi)其他節(jié)點(diǎn)的相關(guān)連接狀態(tài)。

從時(shí)延角度來說，中繼節(jié)點(diǎn)的選擇應(yīng)以最小化時(shí)延為目標(biāo)，因此，定義網(wǎng)絡(luò)中節(jié)點(diǎn)投遞消息到達(dá)給定節(jié)點(diǎn)j的最小時(shí)延min()P j如式（6）所示。

通過所建立的時(shí)序圖模型，可獲知到達(dá)節(jié)點(diǎn) j的最小時(shí)延，進(jìn)而獲知在整個(gè)網(wǎng)絡(luò)內(nèi)，各個(gè)節(jié)點(diǎn)在消息轉(zhuǎn)發(fā)時(shí)延方面的相對(duì)能力，即時(shí)延度 Wp( i, j)，如式（7）所示，從定義可知，節(jié)點(diǎn)相遇間隔時(shí)間越長，則節(jié)點(diǎn)投遞消息到目標(biāo)節(jié)點(diǎn)的期望時(shí)延越大，即式（7）中 P ( i, j)越大，則其針對(duì)節(jié)點(diǎn)j的時(shí)延度 Wp( i, j)就越小。

同理，從網(wǎng)絡(luò)負(fù)載角度來說，需選擇到達(dá)目標(biāo)節(jié)點(diǎn)跳數(shù)最少的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，利用時(shí)序圖模型，通過式（8）可獲知到達(dá)節(jié)點(diǎn)j所需的最小跳數(shù)。

節(jié)點(diǎn)i針對(duì)j在轉(zhuǎn)發(fā)跳數(shù)方面的相對(duì)能力，即中繼度g(,)W i j如式（9）所示。

節(jié)點(diǎn)i轉(zhuǎn)發(fā)消息到達(dá)節(jié)點(diǎn)j所需的平均跳數(shù)越多，即式（9）中 G ( i, j)越大，則其對(duì)節(jié)點(diǎn)j的中繼度 Wg( i, j)越弱，經(jīng)節(jié)點(diǎn)i轉(zhuǎn)發(fā)消息到j(luò)的網(wǎng)絡(luò)開銷越大。

與時(shí)延和跳數(shù)不同，針對(duì)節(jié)點(diǎn)j的相對(duì)可達(dá)率Vmax(j)可定義為網(wǎng)絡(luò)中的所有節(jié)點(diǎn)在有限次機(jī)會(huì)內(nèi)與節(jié)點(diǎn)j相遇的最大概率，如式（10）所示。

進(jìn)而，節(jié)點(diǎn)i轉(zhuǎn)發(fā)消息到節(jié)點(diǎn)j的能力，即可達(dá)度 Wv( i, j)如式（11）所示，節(jié)點(diǎn)i轉(zhuǎn)發(fā)消息到達(dá)節(jié)點(diǎn)j的相對(duì)可達(dá)率 V ( i, j)越大，則可達(dá)度 Wv( i, j)越高，經(jīng)該節(jié)點(diǎn)成功轉(zhuǎn)發(fā)消息到達(dá)節(jié)點(diǎn) j的概率越大。

4.2 節(jié)點(diǎn)轉(zhuǎn)發(fā)消息效用值均衡及量化方法

機(jī)會(huì)網(wǎng)絡(luò)的網(wǎng)絡(luò)性能與所采取的消息傳輸策略直接相關(guān)，其中，中繼節(jié)點(diǎn)的選擇至關(guān)重要，需要綜合考慮時(shí)延度、中繼度與可達(dá)度3個(gè)方面因素，使所提消息傳輸策略獲得較好的網(wǎng)絡(luò)性能。

對(duì)于由三維向量組成的空間來說，若將一組由3個(gè)空間向量構(gòu)成的線性無關(guān)向量組作為基底，則該幾何空間中的任意元素都可以唯一地表示成這一向量組的線性組合[14]。以本節(jié)點(diǎn)為坐標(biāo)原點(diǎn)，與3個(gè)不共面的向量構(gòu)成空間的一個(gè)仿射標(biāo)架，如圖 2 所示。

圖2 節(jié)點(diǎn)轉(zhuǎn)發(fā)消息效用度抽象模型

假設(shè)時(shí)延度與中繼度共線，則可推得式（12）。

進(jìn)而，得到式（13）。

由式（1）、式（3）、式（5）~式（8）可進(jìn)一步推得式（14）。

根據(jù)時(shí)序圖 GTk中對(duì) p ( i, j, Tk,null)及 g ( i, j, Tk,null)的定義可知，不存在同一λ使得 p ( i, j,Tk,null)與 g ( i, j, Tk,null)在不同的 Tk時(shí)刻均滿足線性關(guān)系，因此，時(shí)延度與中繼度不共線。同理可證得可達(dá)度與中繼度不共線。

若 K1，K2，K3中，最后一個(gè)不為零的數(shù)為 Kn，顯然 n ≠ 1，若 n = 1 ，因，故

若 K2≠ 0 ，則，即，與所得不共線矛盾，故 K2= 0 。

再設(shè) K3≠ 0 ， ? =- K1K3， β =-K2K3，則存在唯一的實(shí)數(shù)對(duì)（? , β ）滿足式（16）。

由此可知，

由式（4）、式（8）、式（9）可進(jìn)一步推得式（17）。

由 g ( i, j, Tk,null)的定義可知，在不同的 Tk， Tj時(shí)刻， g ( i, j, Tk,null)取值不同，因此，不存在唯一的實(shí)數(shù)對(duì)（? , β ）滿足式（16），故 K3= 0 ，不存在不全為零的數(shù)使得式（15）成立。因此，為線性無關(guān)向量組，則節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的效用度就可由個(gè)向量唯一的表示。

為滿足不同場(chǎng)景下的需求，實(shí)現(xiàn)網(wǎng)絡(luò)性能的動(dòng)態(tài)可控調(diào)整，定義αm,m = p, v, g分別為時(shí)延度、中繼度及可達(dá)度對(duì)節(jié)點(diǎn)轉(zhuǎn)發(fā)消息效用度的影響因子，且三者滿足式（19）所示歸一化條件。

由此，節(jié)點(diǎn)轉(zhuǎn)發(fā)消息效用值 Q ( i, j)的計(jì)算方法如式（20）所示。通過調(diào)整αm，并對(duì)節(jié)點(diǎn)投遞消息的時(shí)延度、中繼度及可達(dá)度取模，實(shí)現(xiàn)對(duì)效用值Q( i, j)的動(dòng)態(tài)均衡。

不同節(jié)點(diǎn)轉(zhuǎn)發(fā)消息到達(dá)目標(biāo)節(jié)點(diǎn)的能力差異程度無法由單個(gè)節(jié)點(diǎn)的態(tài)勢(shì)體現(xiàn)，均勻量化的方法只在量化初始值為均勻分布時(shí)才能達(dá)到最佳效果，而機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)具有隨機(jī)性，無法確定根據(jù)節(jié)點(diǎn)相遇時(shí)間信息得出的消息轉(zhuǎn)發(fā)效用值服從[0,1]內(nèi)的均勻分布，因此，本文采用適用于絕大多數(shù)情況的非均勻量化的方法[15]，如式（21）所示。

其中，Q為輸入量化值， Q '為量化輸出值。β為常數(shù)，它決定了量化器的壓擴(kuò)程度。針對(duì)目標(biāo)節(jié)點(diǎn)的Q值越大，則量化輸出值 Q '越高，其轉(zhuǎn)發(fā)消息到達(dá)目標(biāo)節(jié)點(diǎn)的能力越強(qiáng)。隨機(jī)運(yùn)動(dòng)過程中，相遇的節(jié)點(diǎn)利用量化效用值感知自身與對(duì)方節(jié)點(diǎn)轉(zhuǎn)發(fā)消息能力的差異，進(jìn)而對(duì)消息的轉(zhuǎn)發(fā)進(jìn)行分布式?jīng)Q策，直至消息到達(dá)目的節(jié)點(diǎn)。

所提出消息傳輸機(jī)制的偽代碼如下。

5 仿真驗(yàn)證及結(jié)果分析

本文采用機(jī)會(huì)網(wǎng)絡(luò)環(huán)境(ONE, opportunistic network environment)[16~18]仿真平臺(tái)驗(yàn)證所提出機(jī)制的有效性，并與典型的多副本路由機(jī)制 Epidemic以及單副本路由機(jī)制PROPHET進(jìn)行對(duì)比。仿真參數(shù)設(shè)置如表 2所示。本文選取 ?p= 0 .45， ?v= 0 .35，?g= 0 .2。

表2 仿真參數(shù)設(shè)置

5.1 節(jié)點(diǎn)數(shù)量對(duì)傳輸策略影響分析

顯然，在給定網(wǎng)絡(luò)區(qū)域及節(jié)點(diǎn)移動(dòng)速度后，節(jié)點(diǎn)相遇總次數(shù)與節(jié)點(diǎn)的個(gè)數(shù)直接相關(guān)。本部分主要驗(yàn)證節(jié)點(diǎn)數(shù)量變化對(duì)所提出的CSAMT消息傳輸策略的影響情況，其中主要包括網(wǎng)絡(luò)負(fù)載率、消息成功投遞率及消息平均時(shí)延3個(gè)方面。

CSAMT、PROPHET、Epidemic的負(fù)載率如上圖3所示。結(jié)果表明網(wǎng)絡(luò)負(fù)載率隨節(jié)點(diǎn)數(shù)量的增加而逐漸上升，3種消息傳輸策略中，CSAMT增長幅度遠(yuǎn)小于 PROPHET與 Epidemic。CSAMT較PROPHET與Epidemic在網(wǎng)絡(luò)負(fù)載率方面平均降低了48.3%以上，且由圖3所示曲線可知：增加節(jié)點(diǎn)數(shù)量會(huì)使得CSAMT較PROPHET與Epidemic在負(fù)載率性能增益上進(jìn)一步提高。

圖3 不同節(jié)點(diǎn)個(gè)數(shù)下負(fù)載率的比較

節(jié)點(diǎn)個(gè)數(shù)對(duì)消息成功投遞率的影響如圖 4所示，隨著節(jié)點(diǎn)數(shù)量的增加，CSAMT、PROPHET、Epidemic三者的消息成功投遞率都呈上升趨勢(shì)，當(dāng)節(jié)點(diǎn)個(gè)數(shù)為85時(shí)，CSAMT較其他兩者有大約5.6%的性能提升，且由圖4可知，節(jié)點(diǎn)數(shù)量的增加會(huì)使CSAMT在投遞率方面的優(yōu)勢(shì)更為明顯。

圖4 不同節(jié)點(diǎn)個(gè)數(shù)下消息成功投遞率的比較

圖5描述了節(jié)點(diǎn)個(gè)數(shù)對(duì)消息傳輸時(shí)延的影響情況，CSAMT、PROPHET及 Epidemic的消息平均時(shí)延都隨著節(jié)點(diǎn)數(shù)量的增加而快速下降。當(dāng)節(jié)點(diǎn)個(gè)數(shù)為55時(shí)，CSAMT比 PROPHET的時(shí)延減小約7.8%，僅較Epidemic略差。節(jié)點(diǎn)個(gè)數(shù)大于55時(shí)，CSAMT較PROPHET性能增益幅度逐漸減小，到95個(gè)節(jié)點(diǎn)時(shí)兩者的時(shí)延性能已基本相當(dāng)。

圖5 不同節(jié)點(diǎn)個(gè)數(shù)下消息平均時(shí)延的比較

由上述結(jié)果可知，當(dāng)節(jié)點(diǎn)采用PROPHET機(jī)制進(jìn)行消息傳輸時(shí)，雖然節(jié)點(diǎn)數(shù)量的增加使得各個(gè)節(jié)點(diǎn)能夠獲知較多的相遇概率信息，但是如前所述，該機(jī)制沒有考慮到節(jié)點(diǎn)間鏈路出現(xiàn)的時(shí)間順序，過高地估計(jì)了節(jié)點(diǎn)之間的連接性，因此，消息轉(zhuǎn)發(fā)次數(shù)較多，使得網(wǎng)絡(luò)負(fù)載率隨節(jié)點(diǎn)數(shù)量增加而急劇上升，同時(shí)，PROPHET與Epidemic對(duì)于中繼節(jié)點(diǎn)選擇的不合理性也限制了消息投遞率、時(shí)延及網(wǎng)絡(luò)負(fù)載的性能提升；另外，對(duì)于多副本傳輸策略 Epidemic來說，中繼節(jié)點(diǎn)的選擇過程并未考慮節(jié)點(diǎn)之間的連接態(tài)勢(shì)，而是利用所有節(jié)點(diǎn)間的相遇機(jī)會(huì)，節(jié)點(diǎn)以泛洪的方式將消息副本在網(wǎng)絡(luò)中進(jìn)行擴(kuò)散，雖然能夠獲得相對(duì)較小的時(shí)延，但是極大地浪費(fèi)了有限的網(wǎng)絡(luò)資源。所提出的CSAMT傳輸策略中，節(jié)點(diǎn)根據(jù)保存的歷史信息建立模型估計(jì)節(jié)點(diǎn)間連接出現(xiàn)的態(tài)勢(shì)，從而更加準(zhǔn)確地選擇中繼節(jié)點(diǎn)，有效地避免了消息在網(wǎng)絡(luò)中盲目地傳輸，且該機(jī)制的擴(kuò)展性較好。隨著節(jié)點(diǎn)數(shù)量的增加，節(jié)點(diǎn)間相遇次數(shù)增多，CSAMT機(jī)制即可由感知的網(wǎng)絡(luò)狀態(tài)演進(jìn)趨勢(shì)，更好地利用節(jié)點(diǎn)移動(dòng)帶來的通信機(jī)會(huì)投遞消息，因而雖節(jié)點(diǎn)數(shù)量增多，但其負(fù)載率依然較低，能夠更好地適應(yīng)資源受限的機(jī)會(huì)網(wǎng)絡(luò)。

5.2 緩存空間對(duì)傳輸策略影響分析

節(jié)點(diǎn)的緩存容量決定了節(jié)點(diǎn)可攜帶的消息數(shù)量，機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)緩存容量通常是非常有限的，如何利用有限的節(jié)點(diǎn)緩存容量更有效地完成對(duì)消息的中繼轉(zhuǎn)發(fā)是機(jī)會(huì)網(wǎng)絡(luò)消息傳輸策略的研究重點(diǎn)。本部分主要分析節(jié)點(diǎn)緩存容量的變化對(duì)CSAMT消息傳輸策略的影響。

不同緩存空間下 CSAMT、PROPHET與Epidemic的網(wǎng)絡(luò)負(fù)載率如圖 6所示，CSAMT、PROPHET、Epidemic的負(fù)載率均呈現(xiàn)快速下降趨勢(shì)，且 CSAMT的負(fù)載率一直較 PROPHET與Epidemic低49.5%以上，充分表明了CSAMT相比兩者在降低網(wǎng)絡(luò)負(fù)載方面的優(yōu)勢(shì)。

圖6 不同緩存空間下負(fù)載率的比較

節(jié)點(diǎn)緩存空間對(duì) CSAMT、PROPHET與Epidemic的消息成功投遞率的影響如圖7所示，隨著節(jié)點(diǎn)緩存空間的逐漸增加，3種算法的投遞率均呈快速上升趨勢(shì)。緩存空間較為有限時(shí)，CSAMT的投遞率優(yōu)于PROPHET及Epidemic，在緩存空間為8MB時(shí)CSAMT較兩者提高14.9%以上，隨著緩存空間進(jìn)一步增加，CSAMT策略的性能增益有所降低。

圖7 不同緩存空間下投遞率的比較

圖8描述了緩存空間變化對(duì)消息平均時(shí)延的影響，從結(jié)果中可知，增加節(jié)點(diǎn)緩存空間可以減少PROPHET與Epidemic的消息平均時(shí)延，而CSAMT算法的時(shí)延則趨于穩(wěn)定，且一直較PROPHET小，其中，當(dāng)緩存空間為6MB時(shí)，CSAMT較PROPHET的平均時(shí)延減少了13.4%。隨著緩存空間的逐漸加大，PROPHET的時(shí)延性能逐漸接近CSAMT，但最終仍較CSAMT略差。

圖8 不同緩存空間下消息平均時(shí)延的比較

由上述結(jié)果可知，增大節(jié)點(diǎn)緩存空間可以增加節(jié)點(diǎn)攜帶的消息數(shù)量，使得相遇的節(jié)點(diǎn)間可傳遞的消息數(shù)量增多，同等連接狀況下，消息遇到目標(biāo)節(jié)點(diǎn)的概率增大，從而有效提升了消息的投遞率和平均時(shí)延性能。如前所述，PROPHET機(jī)制雖然可由歷史信息進(jìn)行相遇概率預(yù)測(cè)，但PROPHET忽視了節(jié)點(diǎn)相遇的時(shí)間先后順序，沒有準(zhǔn)確地把握連接的演進(jìn)趨勢(shì)，過高地估計(jì)了鏈路的可用性，造成消息不合理的轉(zhuǎn)發(fā)次數(shù)過多，雖然消息被投遞的概率增大，卻因中繼節(jié)點(diǎn)的選擇不合理，造成較差的投遞率與平均時(shí)延性能以及較高的網(wǎng)絡(luò)負(fù)載。Epidemic機(jī)制的洪泛策略將網(wǎng)絡(luò)中消息副本的冗余度最大化，雖可獲得較好的消息投遞率與平均時(shí)延性能，但其未考慮節(jié)點(diǎn)鏈接的演進(jìn)趨勢(shì)，造成對(duì)網(wǎng)絡(luò)資源的極大浪費(fèi)。所提出的CSAMT消息轉(zhuǎn)發(fā)機(jī)制通過建立時(shí)序圖模型，能夠由獲知的節(jié)點(diǎn)移動(dòng)規(guī)律及網(wǎng)絡(luò)拓?fù)溲葸M(jìn)趨勢(shì)，充分考慮節(jié)點(diǎn)之間的負(fù)載度、中繼度和可達(dá)度3個(gè)方面因素，進(jìn)而估算節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的效用值，實(shí)現(xiàn)中繼節(jié)點(diǎn)選擇過程的分布式?jīng)Q策，從而有效地降低了消息轉(zhuǎn)發(fā)過程中參與協(xié)作緩存的節(jié)點(diǎn)數(shù)量，達(dá)到了降低網(wǎng)絡(luò)負(fù)載的目的；同時(shí)，各個(gè)節(jié)點(diǎn)的緩存利用率也隨之上升。中繼節(jié)點(diǎn)選擇過程中，節(jié)點(diǎn)充分地考慮了網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)之間的連通情況，所選擇的中繼節(jié)點(diǎn)能夠以較高的概率到達(dá)目的節(jié)點(diǎn)，實(shí)現(xiàn)了消息投遞率和時(shí)延性能上的增益，有效地改善了網(wǎng)絡(luò)性能。

6 結(jié)束語

為充分利用機(jī)會(huì)網(wǎng)絡(luò)受限的網(wǎng)絡(luò)資源，進(jìn)一步改善網(wǎng)絡(luò)性能，本文提出了一種節(jié)點(diǎn)連接態(tài)勢(shì)感知的消息傳輸策略。首先根據(jù)建立的時(shí)序圖模型對(duì)節(jié)點(diǎn)移動(dòng)規(guī)律進(jìn)行感知，進(jìn)而分析節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的能力，并利用所提出的均衡方法進(jìn)行均衡、量化，得到節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的效用值，最后，綜合考慮負(fù)載度、中繼度和可達(dá)度3個(gè)方面因素選擇中繼節(jié)點(diǎn)。仿真結(jié)果表明，本文提出的CSAMT消息傳輸策略能夠有效地提高消息成功投遞率，降低消息平均時(shí)延，并大幅降低網(wǎng)絡(luò)負(fù)載，即可利用較少的網(wǎng)絡(luò)資源達(dá)到較高的性能增益，完全滿足機(jī)會(huì)網(wǎng)絡(luò)資源受限情況下進(jìn)行消息傳輸?shù)囊蟆?/p>

[1] 董超, 錢睿, 陳貴海等. 無線自組織網(wǎng)絡(luò)中流間網(wǎng)絡(luò)編碼機(jī)會(huì)發(fā)現(xiàn)方法的研究[J]. 通信學(xué)報(bào), 2011, 32(10): 92-98.DONG C, QIAN R, CHEN G H, et al. Method for discovering in-tra-session network coding opportunity in wireless ad hoc networks[J].Journal on Communications, 2011, 32(10):92-98.

[2] MORGAN Y L. Notes on DSRC & WAVE standards suite: its architecture, design, and characteristics[J]. IEEE Communications Surveys& Tutorials, 2010, 12(4): 504-518.

[3] JUANG P, OKI H, WANG Y, et al. Energy-efficient computing for wildlife tracking: design trade-offs and early experiences with Zebra-Net[J]. ACM SIGARCH Computer Architecture News, 2002,37(10): 96-107.

[4] SMALL T, HAADS Z J. The shared wireless infostation model: a new ad hoc networking paradigm[A]. Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing.Annapolis[C]. Annapolis, MD, USA, 2003.233-244.

[5] PENTLAND A, FLETCHER R, HASSON A. DakNet: rethinking connectivity in developing nations[J]. Computer, 2004, 37(1): 78-83．

[6] DORIA A, UDEN M, PANDEY D P. Providing connectivity to the saami nomadic community[A]. Proceedings of the 2nd International Conference on Open Collaborative Design for Sustainable Innovation[C]. Bangalore, India, 2002.

[7] 聶志, 劉靜, 甘小鶯等. 移動(dòng)ad hoc網(wǎng)絡(luò)中機(jī)會(huì)路由轉(zhuǎn)發(fā)策略的研究[J].重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 2010, 22(4): 421-425.NIE Z, LIU J, GAN X Y, et al. A relay node selection technique for opportunistic routing in mobile ad hoc networks[J]. Journal of Chongqing University of Posts and Telecommunications, 2010, 22(4):421-425.

[8] 熊永平, 孫利民, 牛建偉等. 機(jī)會(huì)網(wǎng)絡(luò)[J]. 軟件學(xué)報(bào), 2009, 20(1):124-137.XIONG Y P, SUN L M, NIU J W, et al. Opportunistic networks[J].Journal of Software, 2009, 20(1): 124-137.

[9] THRASYVOULOS S, KONSTANTINOS P, CAULIGI S R. Efficient routing in intermittently connected mobile networks: the multiple-copy case[J]. IEEE/ACM Transactions on Networking, 2008, 16(1): 77-90.

[10] THRASYVOULOS S, KONSTANTINOS P, CAULIGI S R. Efficient routing in intermittently connected mobile networks: the single-copy case[J]. IEEE/ACM Transactions on Networking, 2008, 16(1): 63-76.

[11] ANDERS L, AVRI D, OLOV S. Probabilistic routing in intermittently connected networks[A]. ACM SIGMOBILE Mobile Computing and Communications Review[C]. New York, NY, USA, 2003, 7(3):19-20.

[12] 卓瑩, 龔春葉, 龔正虎. 網(wǎng)絡(luò)傳輸態(tài)勢(shì)感知的研究與實(shí)現(xiàn)[J]. 通信學(xué)報(bào), 2010, 31(9): 54-63.ZHUO Y, GONG C Y, GONG Z H. Research and implementation of network transmission situation awareness[J]. Journal on Communications,2010, 31(9): 54-63.

[13] VASSILIS K. Sequence diagramsgraphs[J]. Physica A: Statistical Mechanics and Its Applications, 2009, 388(6):1007-1023.

[14] 潘國榮, 趙鵬飛. 基于空間向量的三維基準(zhǔn)轉(zhuǎn)換模型[J]. 大地測(cè)量與地球動(dòng)力學(xué), 2009, 29(6): 79-82.PAN G R, ZHAO P F. 3D datum transformation model based on space vector[J]. Journal of Geodesy and Geodynamics, 2009, 29(6): 79-82.

[15] WEI D, HOA V P, OLGICA M. Distortion-rate functions for quantized compressive sensing[A]. IEEE Workshop on Networking and Information Theory[C]. Greece, 2009.171-175.

[16] KER?NEN A, OTT J, K?RKK?INEN T. The ONE simulator for DTN protocol evaluation[A]. The 2nd International Conference on Simulation Tools and Techniques[C]. Rome, Italy, 2009. 1-10.

[17] VASCON G J W, FARID FARAHMAND, JQEL JOSE P C R. Retiring replicants: congestion control for intermittently-connected networks[A].IEEE Proceedings INFOCOM[C]. San Diego, USA, 2010. 1-9.

[18] VASCON G J S, FARID FARAHMAND, JQEL JOSE P C R. Impact of vehicle movement models on VDTN routing strategies for rural connectivity[J]. International Journal of Mobile Network Design and Innovation, 2009, 3(2): 103-111.