， ，

(中國(guó)電子科學(xué)研究院，北京 100041)

0 引 言

無(wú)線Mesh網(wǎng)絡(luò)(Wireless Mesh Network, WMN)最初是美軍為滿足軍事信息系統(tǒng)中寬帶數(shù)據(jù)傳輸以及支持端到端IP、語(yǔ)音和視頻信息、不采用GPS實(shí)現(xiàn)精確定位要求而建立的[1]。近年來(lái)，因其具有易部署、高帶寬、結(jié)構(gòu)靈活和抗毀性強(qiáng)等特點(diǎn)而成為國(guó)內(nèi)外研究熱點(diǎn)，特別是在軍事領(lǐng)域，其特性能夠滿足高帶寬、高機(jī)動(dòng)性、超視距的保障能力要求。因此，如何將軍事信息系統(tǒng)的通信要求與無(wú)線Mesh網(wǎng)絡(luò)的特點(diǎn)進(jìn)行結(jié)合，尋求最優(yōu)的應(yīng)用配置，是值得深入研究的問題。

無(wú)線Mesh網(wǎng)絡(luò)是一種多跳的分布式網(wǎng)絡(luò)，如圖1所示，典型的無(wú)線Mesh網(wǎng)絡(luò)通常包含兩類節(jié)點(diǎn): Mesh路由器(Mesh Router, MR)和Mesh客戶端(Mesh Client, MC)。在大部分的WMN應(yīng)用中，Mesh路由器因其固定性而構(gòu)成網(wǎng)絡(luò)骨干[2]。將WMN技術(shù)應(yīng)用于軍事信息系統(tǒng)，可以解決極端環(huán)境下的無(wú)線組網(wǎng)問題。然而在軍事信息系統(tǒng)中，尤其是在戰(zhàn)場(chǎng)環(huán)境下，往往存在無(wú)線網(wǎng)絡(luò)資源受限問題，進(jìn)而導(dǎo)致使用WMN進(jìn)行信息分發(fā)將面臨網(wǎng)絡(luò)瓶頸問題[3]。在無(wú)線Mesh網(wǎng)絡(luò)中，Mesh路由器相對(duì)于Mesh客戶端具有相對(duì)固定性和大容量的特性，因此可以引入內(nèi)容分發(fā)(Content Delivery)技術(shù)[4]，將Mesh路由器作為鏡像服務(wù)器，以提升無(wú)線網(wǎng)絡(luò)資源受限條件下軍事信息系統(tǒng)中信息分發(fā)的服務(wù)質(zhì)量。

圖1 無(wú)線Mesh網(wǎng)絡(luò)架構(gòu)

通過(guò)將內(nèi)容分發(fā)技術(shù)引入到無(wú)線Mesh網(wǎng)絡(luò)中，內(nèi)容對(duì)象的鏡像被分發(fā)至靠近相關(guān)MC的MR中，MC發(fā)出的數(shù)據(jù)信息請(qǐng)求可以被就近服務(wù)。從MC發(fā)出的數(shù)據(jù)信息請(qǐng)求被重定向至最近的擁有相應(yīng)鏡像的MR，MR將所需的數(shù)據(jù)信息通過(guò)響應(yīng)消息回傳給MC。由此可見，內(nèi)容鏡像的分發(fā)直接決定了無(wú)線Mesh網(wǎng)絡(luò)的服務(wù)質(zhì)量。以往對(duì)于內(nèi)容分發(fā)技術(shù)的研究聚焦于如何通過(guò)鏡像分發(fā)機(jī)制降低網(wǎng)絡(luò)中的數(shù)據(jù)獲取延遲，設(shè)計(jì)的方法更適用于便于集中控制和計(jì)算的有線網(wǎng)絡(luò)環(huán)境，未考慮無(wú)線Mesh網(wǎng)絡(luò)的分布式特點(diǎn)，如此建立的問題模型并不能真正反映無(wú)線Mesh網(wǎng)絡(luò)中內(nèi)容分發(fā)的實(shí)際情況。因此對(duì)于無(wú)線Mesh網(wǎng)絡(luò)中的內(nèi)容分發(fā)方法的研究，對(duì)于構(gòu)建基于無(wú)線Mesh網(wǎng)絡(luò)的軍事信息系統(tǒng)具有重要意義。

本文研究了軍事信息系統(tǒng)中基于無(wú)線Mesh網(wǎng)絡(luò)的內(nèi)容分發(fā)方法，旨在提升無(wú)線網(wǎng)絡(luò)資源受限條件下軍事信息系統(tǒng)中信息分發(fā)的服務(wù)質(zhì)量。首先，基于無(wú)線Mesh網(wǎng)絡(luò)，設(shè)計(jì)了立體化的軍事情報(bào)信息中心-戰(zhàn)術(shù)通信衛(wèi)星-小型分布式地面站-作戰(zhàn)單元網(wǎng)絡(luò)結(jié)構(gòu)模型。在該網(wǎng)絡(luò)模型的基礎(chǔ)上，我們對(duì)軍事信息系統(tǒng)中的基于無(wú)線Mesh網(wǎng)絡(luò)的內(nèi)容分發(fā)問題進(jìn)行了形式化地描述。針對(duì)該問題，本文設(shè)計(jì)了分布式四階段啟發(fā)式算法。該方法根據(jù)軍事信息系統(tǒng)中各類型內(nèi)容被訂閱的熱度，采用分布式的算法，將軍事情報(bào)信息中心的內(nèi)容鏡像分發(fā)至相應(yīng)的分布式地面站，以提高基于無(wú)線Mesh網(wǎng)絡(luò)的軍事信息系統(tǒng)的服務(wù)質(zhì)量。

1 相關(guān)研究

無(wú)線Mesh網(wǎng)絡(luò)最初是美軍為滿足軍事通信中無(wú)線帶寬數(shù)據(jù)傳輸?shù)纫蠼⒌?，因其組網(wǎng)快速靈活、抗毀性強(qiáng)等特點(diǎn)，在軍事信息系統(tǒng)組網(wǎng)中得到廣泛的應(yīng)用。文獻(xiàn)[5]提出了基于802.16 d的無(wú)線Mesh網(wǎng)絡(luò)的集團(tuán)軍戰(zhàn)役指揮所通信系統(tǒng)。系統(tǒng)具有保密、易于開設(shè)使用和建網(wǎng)費(fèi)用低廉等特點(diǎn)。文獻(xiàn)[6]提出了一種海戰(zhàn)場(chǎng)環(huán)境下基于Mesh結(jié)構(gòu)的無(wú)線網(wǎng)絡(luò)應(yīng)用方案，滿足艦艇編隊(duì)通信網(wǎng)絡(luò)高速率、大容量、非視距傳輸?shù)囊?，?duì)無(wú)線Mesh網(wǎng)絡(luò)在軍事通信領(lǐng)域的深入研究具有一定的參考價(jià)值。

然而，無(wú)論實(shí)在軍事應(yīng)用領(lǐng)域，還是學(xué)術(shù)領(lǐng)域，將內(nèi)容分發(fā)技術(shù)引入到無(wú)線Mesh網(wǎng)絡(luò)用于解決網(wǎng)絡(luò)瓶頸的研究都很少。就我們的了解而言，對(duì)無(wú)線Mesh網(wǎng)絡(luò)中內(nèi)容分發(fā)技術(shù)的相關(guān)研究，主要有以下文獻(xiàn)。在文獻(xiàn)[7]中，作者證明了最優(yōu)的內(nèi)容鏡像分發(fā)策略是每個(gè)內(nèi)容對(duì)象的副本數(shù)量正比于pr0.667，其中pr是內(nèi)容對(duì)象的熱度。文獻(xiàn)[8]中，作者對(duì)無(wú)線覆蓋網(wǎng)絡(luò)中的內(nèi)容分發(fā)模型做了較為完備的理論分析，但是并沒有提出具體的內(nèi)容分發(fā)方法。

2 模型與定義

2.1 網(wǎng)絡(luò)模型

軍事信息系統(tǒng)通信網(wǎng)絡(luò)在戰(zhàn)時(shí)要覆蓋整個(gè)作戰(zhàn)區(qū)域，而且作戰(zhàn)單元快速移動(dòng)，要求一定要采用無(wú)線通信的方式;通信系統(tǒng)要具備較強(qiáng)的抗毀性，不能因?yàn)閭€(gè)別節(jié)點(diǎn)的毀壞而導(dǎo)致整個(gè)通信系統(tǒng)的癱瘓，要求一種無(wú)中心、分布式的方式進(jìn)行組網(wǎng)。因此，我們?cè)O(shè)計(jì)了如圖2所示的基于無(wú)線Mesh網(wǎng)絡(luò)的軍事信息系統(tǒng)。軍事信息情報(bào)中心通過(guò)戰(zhàn)術(shù)通信衛(wèi)星與廣泛分布小型分布式地面戰(zhàn)進(jìn)行通信，而地理分布鄰接的小型分布式地面站之間可使用長(zhǎng)距離無(wú)線通信技術(shù)(例如LoRa等)進(jìn)行通信。另外，小型分布式地面站采用無(wú)線的方式與周圍一定范圍內(nèi)的作戰(zhàn)單元通信，距離較近的作戰(zhàn)單元可直接與小型分布式地面站進(jìn)行通信，距離較遠(yuǎn)的作戰(zhàn)單元通過(guò)短距離無(wú)線通信技術(shù)(例如D2D等)組成多跳的無(wú)線Mesh網(wǎng)絡(luò)與小型分布式地面站進(jìn)行通信。在這樣的網(wǎng)絡(luò)結(jié)構(gòu)中，小型分布式地面站充當(dāng)了無(wú)線Mesh網(wǎng)絡(luò)中的MR，構(gòu)成網(wǎng)絡(luò)骨干;各作戰(zhàn)單元充當(dāng)了MC，通過(guò)自組網(wǎng)的方式與小型分布式地面站建立通信。

圖2 基于無(wú)線Mesh網(wǎng)絡(luò)的軍事信息系統(tǒng)

由于內(nèi)容分發(fā)技術(shù)的引入，可以將小型分布式地面站作為鏡像服務(wù)器，情報(bào)信息中心根據(jù)各作戰(zhàn)單元對(duì)于各項(xiàng)內(nèi)容的訂閱情況，統(tǒng)計(jì)各項(xiàng)內(nèi)容的熱度信息，將內(nèi)容鏡像分發(fā)至相應(yīng)的分布式地面站，以便各作戰(zhàn)單元可以就近獲取所需的內(nèi)容。對(duì)于軍事信息系統(tǒng)中的內(nèi)容和節(jié)點(diǎn)，我們給出如下形式的定義。

定義1 內(nèi)容對(duì)象集合。軍事信息系統(tǒng)中的內(nèi)容被劃分為若干個(gè)內(nèi)容對(duì)象，所有內(nèi)容對(duì)象組成內(nèi)容對(duì)象全集O，該集合可表示為O={Obj1,Obj2,...,Objk,...}，其中內(nèi)容對(duì)象Objk的熱度為prk，容量大小為sk。

定義2 通信節(jié)點(diǎn)集合。所有的作戰(zhàn)單元組成了CU集合，即M={CU1,CU2,...,CUm,...};所有的小型分布式地面站組成了GS集合N，即N={GS1,GS2,...,GSn,...}。

在合理的內(nèi)容分發(fā)策略下，情報(bào)信息中心根據(jù)各內(nèi)容對(duì)象的訂閱情況，將內(nèi)容對(duì)象的鏡像分發(fā)至小型分布式地面站，由于各地面站的存儲(chǔ)能力有限，每個(gè)地面站只能存儲(chǔ)部分的內(nèi)容鏡像。為了簡(jiǎn)化網(wǎng)絡(luò)模型，可以假設(shè)所有的小型分布式地面站擁有共同的存儲(chǔ)容量SC。在我們?cè)O(shè)計(jì)的多跳無(wú)線Mesh網(wǎng)絡(luò)中，不同節(jié)點(diǎn)之間的通信延遲存在較大的差異，假設(shè)作戰(zhàn)單元CUm與地面站GSn之間傳輸內(nèi)容對(duì)象Objk的通信延遲為dmn(k)(?m∈M,n∈N,k∈O)。由于內(nèi)容訂閱情況的細(xì)微變化不會(huì)對(duì)信息系統(tǒng)的整體傳輸時(shí)延產(chǎn)生太大的影響，因此可以設(shè)置內(nèi)容分發(fā)周期，在每個(gè)周期開始時(shí)重新對(duì)各地面戰(zhàn)的內(nèi)容分發(fā)策略進(jìn)行更新。在周期內(nèi)，當(dāng)某個(gè)內(nèi)容對(duì)象發(fā)生更新時(shí)，情報(bào)信息中心將更新的內(nèi)容鏡像分發(fā)至相應(yīng)的地面站，然后各地面站根據(jù)就近服務(wù)原則將內(nèi)容更新推送至訂閱了該內(nèi)容的作戰(zhàn)單元。

定義3 內(nèi)容更新模型。已有的研究表明[9]，內(nèi)容對(duì)象Objk的更新頻次符合參數(shù)為λk的泊松分布。

在如上述的網(wǎng)絡(luò)模型下，最終到各分布的作戰(zhàn)單元的內(nèi)容分發(fā)由地面站和作戰(zhàn)單元之間協(xié)同完成，緩解了無(wú)線網(wǎng)絡(luò)資源限制引發(fā)的網(wǎng)絡(luò)瓶頸問題。另外，由于分布式地面站緩存了情報(bào)信息中心的內(nèi)容，各作戰(zhàn)單元的主動(dòng)內(nèi)容請(qǐng)求可以在最近的緩存有該內(nèi)容的地面站得到服務(wù)，降低了網(wǎng)絡(luò)的平均請(qǐng)求時(shí)延，提升了軍事信息系統(tǒng)的服務(wù)質(zhì)量。由此可見，設(shè)計(jì)合理的內(nèi)容分發(fā)方法，以決定將哪些內(nèi)容鏡像分發(fā)至哪些分布式地面站，對(duì)基于無(wú)線Mesh網(wǎng)絡(luò)的軍事信息系統(tǒng)的網(wǎng)絡(luò)性能具有關(guān)鍵性的作用。

2.2 問題定義

為了便于描述本文提出的基于無(wú)線Mesh網(wǎng)絡(luò)的內(nèi)容分發(fā)問題，我們引入兩個(gè)決策變量x=[xmnk]和y=[ynk]。其中，ynk=1當(dāng)且僅當(dāng)將內(nèi)容對(duì)象Objk的鏡像分發(fā)至地面站GSn;xmnk=1當(dāng)且僅當(dāng)從地面站GSn將內(nèi)容對(duì)象Objk推送給作戰(zhàn)單元CUm。根據(jù)統(tǒng)計(jì)得出的各內(nèi)容對(duì)象的熱度信息prk(τ)，可以得到單位時(shí)間內(nèi)容更新造成的網(wǎng)絡(luò)中的總傳輸時(shí)延的期望值如下:

(1)

該期望值反映了網(wǎng)絡(luò)中的內(nèi)容分發(fā)延遲，因此可以將其作為內(nèi)容分發(fā)問題的優(yōu)化目標(biāo)。

由于地面站的存儲(chǔ)容量有限，故決策變量y=[ynk]需滿足約束條件：

(2)

另外，為了確保網(wǎng)絡(luò)模型中的就近服務(wù)原則，兩個(gè)決策變量必須滿足如下的約束條件:

(3)

其中Δ是一個(gè)很大的正數(shù)(如Δ=max{dmn})。當(dāng)ynk=0時(shí)，由于Δ很大，故該約束無(wú)效;當(dāng)ynk=1時(shí)，作戰(zhàn)單元CUm必須從最近的擁有相應(yīng)鏡像的地面戰(zhàn)獲取內(nèi)容，否則違反該約束條件。根據(jù)以上分析，可以對(duì)軍事信息系統(tǒng)中基于無(wú)線Mesh網(wǎng)絡(luò)的內(nèi)容分發(fā)問題進(jìn)行如下定義。

定義4 內(nèi)容分發(fā)問題。在分布式地面站容量(2)和就近服務(wù)原則(3)的約束下，將情報(bào)信息中心各內(nèi)容對(duì)象的鏡像分發(fā)至地面站，對(duì)T最小化，以降低無(wú)線Mesh網(wǎng)絡(luò)中傳輸時(shí)延的期望值。

已有的研究表明內(nèi)容分發(fā)問題是NP困難問題，因此定義4中所描述的無(wú)線Mesh網(wǎng)絡(luò)中的內(nèi)容分發(fā)問題也是NP困難問題。在后續(xù)的章節(jié)中，將給出該問題的解決方法并進(jìn)行驗(yàn)證。

3 無(wú)線Mesh網(wǎng)絡(luò)中的內(nèi)容分發(fā)方法

由于該問題的NP困難性，我們無(wú)法求解出該問題的最優(yōu)解。本節(jié)將給出基于貪心策略的分布式四階段啟發(fā)式算法(Four Phase Based Heuristics, FPBH)，用于計(jì)算內(nèi)容分發(fā)策略。根據(jù)各內(nèi)容對(duì)象的訂閱信息，統(tǒng)計(jì)各個(gè)內(nèi)容對(duì)象的熱度，并據(jù)此計(jì)算每個(gè)內(nèi)容對(duì)象所需的鏡像數(shù)目。對(duì)于所需鏡像數(shù)目為p的內(nèi)容對(duì)象，將地面站組成的網(wǎng)絡(luò)骨干進(jìn)行p劃分，在每個(gè)劃分中選擇一個(gè)鏡像分發(fā)位置。由于該方法的分布式特性，不過(guò)度依賴于情報(bào)信息中心的計(jì)算能力，適用于軍事信息系統(tǒng)中無(wú)線Mesh網(wǎng)絡(luò)的內(nèi)容分發(fā)應(yīng)用場(chǎng)景。

3.1 熱度信息收集階段

該階段運(yùn)行于內(nèi)容分發(fā)周期τ，主要目的是收集內(nèi)容對(duì)象的訂閱信息，并根據(jù)該信息計(jì)算各內(nèi)容對(duì)象在下一周期τ+1的熱度，這一階段可分為兩步進(jìn)行。

(1)周期τ期間:每個(gè)地面戰(zhàn)維持一張表，該表用于存儲(chǔ)〈GSn,Objk,subnk〉形式的元組，其中subnk表示地面站GSn處收到的對(duì)于內(nèi)容對(duì)象Objk的訂閱數(shù)。每次有新的訂閱/取消消息到達(dá)GSn時(shí)，該表被更新一次，相應(yīng)的subnk值進(jìn)行+1/-1操作。

(2)周期τ結(jié)束:各地面站將收集到的訂閱信息發(fā)送至情報(bào)信息中心，情報(bào)信息中心據(jù)此統(tǒng)計(jì)各內(nèi)容對(duì)象的熱度，并計(jì)算各內(nèi)容對(duì)象所需的鏡像數(shù)目，廣播至所有的地面站。具體的步驟如下:

(a)各地面站將含有訂閱信息的表發(fā)送至情報(bào)信息中心，然后情報(bào)信息中心整合所有收到的信息。對(duì)于每個(gè)內(nèi)容對(duì)象Objk，根據(jù)公式(4)計(jì)算其熱度:

張家明對(duì)我挺不錯(cuò)的，有吃的喝的第一個(gè)想到我。只是他家里人不大喜歡我。我理解，他們窮是窮了些，但好歹也是本地人，他父母認(rèn)為我是外地來(lái)的，所以對(duì)我不冷不熱。而張家明一直維護(hù)我，說(shuō)我聰明，懂事，而且漂亮。

(4)

(b)由于在文獻(xiàn)[8]中已經(jīng)證明，最優(yōu)的內(nèi)容分發(fā)策略是每個(gè)內(nèi)容對(duì)象Objk的鏡像數(shù)目正比于。因此，在分布式地面站容量SC的約束下，情報(bào)信息中心可以根據(jù)公式(5)計(jì)算Objk在周期τ+1所需的數(shù)目pk。

(5)

(c)情報(bào)信息中心創(chuàng)建一張包含有〈Objk,|Objk|,pk〉形式元組的鏡像列表(Replica List, RL)，并廣播至所有的地面站。該表按pk值進(jìn)行分組，并降序排列。在每組內(nèi)部，元組按內(nèi)容對(duì)象容量大小|Objk|進(jìn)行升序排列，最大化地利用各小型地面站的存儲(chǔ)容量。

3.2 網(wǎng)絡(luò)拓?fù)鋭澐蛛A段

為了充分利用無(wú)線Mesh網(wǎng)絡(luò)的分布式特性，我們對(duì)分布式地面站構(gòu)成的網(wǎng)絡(luò)骨干進(jìn)行拓?fù)鋭澐?，作為本?jié)中分布式的內(nèi)容分發(fā)方法的基礎(chǔ)。因此引入圖劃分算法，對(duì)地面站構(gòu)成的網(wǎng)絡(luò)拓?fù)浞謩e進(jìn)行p劃分，其中p的取值包括所有pk的可能值。圖劃分算法即是將一個(gè)圖劃分為兩個(gè)或者兩個(gè)以上大小基本一致的不相交子集，以使得各個(gè)劃分之間的割邊最少。在每一次圖劃分后，要從該劃分內(nèi)選取一個(gè)領(lǐng)導(dǎo)節(jié)點(diǎn)(Leader Node, LN)，用于運(yùn)行該劃分的內(nèi)容分發(fā)策略生成算法。由于一個(gè)節(jié)點(diǎn)可被選取為多個(gè)劃分的LN節(jié)點(diǎn)，因此選擇LN節(jié)點(diǎn)的原則是挑選該劃分內(nèi)被選取為L(zhǎng)N節(jié)點(diǎn)次數(shù)最少的節(jié)點(diǎn)。

假設(shè)所有地面站構(gòu)成網(wǎng)絡(luò)拓?fù)鋱DG,G(u,v)表示將圖G進(jìn)行u劃分得到的第v個(gè)劃分子圖。對(duì)于劃分G(u,v)，被選取的LN節(jié)點(diǎn)記為L(zhǎng)N(u,v)，該LN節(jié)點(diǎn)在劃分G(u,v)內(nèi)為所需鏡像數(shù)量為u的內(nèi)容對(duì)象選取一個(gè)鏡像分發(fā)位置。結(jié)合以上數(shù)學(xué)符號(hào)，拓?fù)鋭澐蛛A段的算法描述見算法1。

算法1. 網(wǎng)絡(luò)拓?fù)鋭澐炙惴ā?/p>

輸入:圖G,pk。

輸出:包含拓?fù)鋭澐中畔⒌腗ap-List。

1.foru=1→max{pk}do;

3.forv=1→udo

4.if|G(u,v)|=1then

5.LN(u,v)←G(u,v);

6.else

7.LN(u,v)←劃分G(u,v)中被選取次數(shù)最少的點(diǎn);

8.endif

9.endfor

10. 將Map(LN(u,v),G(u,v))添加到Map-List的第u項(xiàng);

12.endfor

圖3 網(wǎng)絡(luò)拓?fù)鋭澐炙惴ㄊ纠?/p>

在算法1中，第2行表示對(duì)圖G進(jìn)行u劃分。由于目前對(duì)于圖劃分算法的研究較為成熟，故其實(shí)現(xiàn)可參考文獻(xiàn)[10]中的快速算法。圖3以地面站數(shù)量為10的網(wǎng)絡(luò)骨干為例，展示了對(duì)拓?fù)浞謩e進(jìn)行1劃分至4劃分及相應(yīng)的LN節(jié)點(diǎn)選取詳情。由于該算法的運(yùn)行需要了解全局的地面戰(zhàn)分布拓?fù)湫畔?，因此該算法的?zhí)行過(guò)程是在情報(bào)信息中心進(jìn)行。在該算法執(zhí)行完畢后，情報(bào)信息中心將得到的Map-List廣播給所有的地面站。由于各分布式地面站組成的骨干網(wǎng)絡(luò)相對(duì)固定，該算法在網(wǎng)絡(luò)部署階段執(zhí)行一次便可。

3.3 分發(fā)策略生成階段

在定義4中我們提到內(nèi)容分發(fā)問題的總體優(yōu)化目標(biāo)是傳輸時(shí)延的期望值T，當(dāng)對(duì)問題進(jìn)行分布式處理時(shí)，必須將優(yōu)化目標(biāo)分布化。對(duì)于需要鏡像數(shù)目為u的內(nèi)容對(duì)象Objk，定義在某個(gè)劃分G(u,v)中，地面站集合為N′，與其關(guān)聯(lián)的作戰(zhàn)單元集合為M'。對(duì)于M'和N'構(gòu)成的子網(wǎng)絡(luò)，可以得到單位時(shí)間內(nèi)容對(duì)象Objk更新造成該子網(wǎng)絡(luò)中的總傳輸時(shí)延的期望值如下:

(5)

結(jié)合該優(yōu)化目標(biāo)，分發(fā)策略生成算法在劃分G(u,v)內(nèi)選擇內(nèi)容對(duì)象Objk的一個(gè)鏡像位置，使得該內(nèi)容對(duì)象的更新在相關(guān)子網(wǎng)絡(luò)里造成的T′(k)最小。

算法2. 分發(fā)策略生成算法。

輸入:集合M,N,O,變量λk,SC,Map-List,RL。

輸出:決策變量y=[ynk]。

1.forevery group in RLdo

2. multicast a message containing the group of object

3. replicas to the corresponding list of LNs in Map-List;

4. upon receiving the message,LN(u,v) will do:

5. lookup the Map-List for theuth item;

6.if|G(u,v)|=1then

8.ynk←1; // n is id of GS

9.endfor

10.else

12.forallObjkin the received groupdo

13. select theGSn0that minimizesT′(k);

14.yn0k←1;

15.endfor

16.endif

17.endfor

策略生成算法的詳細(xì)描述如算法2所示，該算法在熱度信息收集階段結(jié)束后立刻執(zhí)行，以確定下一個(gè)周期的內(nèi)容分發(fā)策略。在該階段，領(lǐng)導(dǎo)節(jié)點(diǎn)LN(u,v)為需要鏡像數(shù)量是u的內(nèi)容對(duì)象在本劃分內(nèi)選擇一個(gè)最佳的鏡像緩存位置。通過(guò)逐個(gè)鏡像位置的選擇，最終生成合理的分發(fā)策略。

3.4 內(nèi)容鏡像分發(fā)階段

在上一階段分發(fā)策略生成后，各分布式地面站立即根據(jù)得到的決策變量y獲取相應(yīng)的內(nèi)容鏡像。該階段的內(nèi)容鏡像分發(fā)，既可采用基于字典服務(wù)[11]的協(xié)作式內(nèi)容分發(fā)，也可采用非協(xié)作式內(nèi)容分發(fā)。以非協(xié)作式內(nèi)容分發(fā)為例，當(dāng)某個(gè)地面站在該周期內(nèi)需要存儲(chǔ)Objk的鏡像時(shí)，若Objk的鏡像已在其緩存中，則不必再向情報(bào)信息中心獲取;否則，從情報(bào)信息中心獲取Objk的鏡像。

縱觀該算法的四個(gè)階段，只有網(wǎng)絡(luò)拓?fù)鋭澐蛛A段算法的執(zhí)行依賴于情報(bào)信息中心，而該算法只有在網(wǎng)絡(luò)部署時(shí)執(zhí)行一次，不影響整體的分布式特點(diǎn)。由于四階段內(nèi)容分發(fā)算法的分布式特性，克服了集中式算法大量的運(yùn)算依賴于中心服務(wù)器的缺陷;同時(shí)，在算法運(yùn)行過(guò)程中，各節(jié)點(diǎn)之間不存在大量的通信消息交互，避免了引入大量的額外通信開銷。

4 仿真實(shí)驗(yàn)

本節(jié)通過(guò)仿真實(shí)驗(yàn)的形式，將我們提出的算法與現(xiàn)有文獻(xiàn)中的內(nèi)容分發(fā)方法進(jìn)行比較，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，以驗(yàn)證我們提出的FPBH的性能。

4.1 實(shí)驗(yàn)環(huán)境

我們使用OMNeT++[12]仿真工具驗(yàn)證測(cè)試本文提出的FPBH算法，生成Mesh拓?fù)浣Y(jié)構(gòu)來(lái)仿真固定的WMN網(wǎng)絡(luò)。隨機(jī)生成的網(wǎng)絡(luò)拓?fù)涔舶?00個(gè)節(jié)點(diǎn)，其中包括25個(gè)地面站和175個(gè)作戰(zhàn)單元。無(wú)線通信協(xié)議設(shè)置為IEEE 802.11 g，通信帶寬為18 Mbps。無(wú)線通信的最大有效距離為140 m，相鄰兩個(gè)節(jié)點(diǎn)之間的平均距離為100 m。

一般來(lái)說(shuō)，內(nèi)容對(duì)象的熱度一般服從Zipf分布，即長(zhǎng)尾分布。在仿真實(shí)驗(yàn)中，地面站依據(jù)參數(shù)為v=0.85的Zipf分布發(fā)出訂閱消息。內(nèi)容對(duì)象的大小符合[0.5→4]MB的均勻分布，而每個(gè)小型地面站的存儲(chǔ)容量為256 MB。雖然實(shí)際中，地面站的存儲(chǔ)容量和內(nèi)容對(duì)象的大小要遠(yuǎn)大于我們實(shí)驗(yàn)中所使用的值，但是增大這些數(shù)值的時(shí)候我們的FPBH算法依然有效。在本次實(shí)驗(yàn)中，我們將FPBH算法與已有的Random和 Lat-CDN[13]進(jìn)行比較。每組實(shí)驗(yàn)中，通過(guò)獨(dú)立10次重復(fù)實(shí)驗(yàn)來(lái)得到平均結(jié)果。我們進(jìn)行了三組實(shí)驗(yàn)來(lái)比較三種不同的性能參數(shù)，即平均請(qǐng)求時(shí)延，網(wǎng)絡(luò)負(fù)載和負(fù)載分布。

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

在第一組實(shí)驗(yàn)中，我們改變網(wǎng)絡(luò)中內(nèi)容更新頻率，對(duì)網(wǎng)絡(luò)中的平均時(shí)延進(jìn)行觀察，實(shí)驗(yàn)結(jié)果如圖4所示。這里所說(shuō)的平均時(shí)延指的是地面站處理完成所有作戰(zhàn)單元相關(guān)更新內(nèi)容推送所消耗的平均時(shí)間，服務(wù)所有的作戰(zhàn)單元消耗總時(shí)間除以數(shù)量。顯而易見，在各組實(shí)驗(yàn)中平均請(qǐng)求時(shí)延都隨著內(nèi)容更新頻率而增長(zhǎng)。我們所提出的FPBH算法的平均時(shí)延增長(zhǎng)速度要慢于其他的方法，也就是說(shuō)FPBH算法時(shí)延性能優(yōu)于其他算法。這是由于FPBH根據(jù)內(nèi)容熱度來(lái)分發(fā)內(nèi)容鏡像，這使得它們要優(yōu)于Random和Lat-CDN。

圖4 平均時(shí)延對(duì)比圖

在接下來(lái)的這組實(shí)驗(yàn)中，我們改變內(nèi)容更新頻率，對(duì)總的網(wǎng)絡(luò)負(fù)載進(jìn)行統(tǒng)計(jì)，網(wǎng)絡(luò)負(fù)載的對(duì)比結(jié)果如圖5所示。實(shí)驗(yàn)結(jié)果顯示網(wǎng)絡(luò)負(fù)載均隨著內(nèi)容更新頻率而增長(zhǎng)， 本文提出的FPBH明顯慢于另外兩種方法。這是因?yàn)镕PBH根據(jù)內(nèi)容熱度來(lái)分發(fā)內(nèi)容鏡像，使得大多數(shù)請(qǐng)求不需要經(jīng)過(guò)太多跳的傳播便能得到服務(wù)，這樣大大減少了網(wǎng)絡(luò)負(fù)載，因此FPBH的網(wǎng)絡(luò)負(fù)載性能優(yōu)于Random和Lat-CDN。

圖5 網(wǎng)絡(luò)負(fù)載對(duì)比圖

在最后這組實(shí)驗(yàn)中，我們將內(nèi)容更新頻率設(shè)置為12，來(lái)觀察網(wǎng)絡(luò)中各地面站的負(fù)載分布情況，結(jié)果如圖6中的箱線圖所示。箱線圖有五個(gè)特征點(diǎn)，分別是上邊緣，上四分位數(shù)，中位數(shù)，下四分位數(shù)和下邊緣。從圖中我們可以看出，三種算法中網(wǎng)絡(luò)負(fù)載分布最差的是Random;由于Lat-CDN根據(jù)傳輸延遲分配副本，因此其負(fù)載分布優(yōu)于Random;考慮到內(nèi)容熱度的FPBH負(fù)載分布明顯優(yōu)于其他方案。另外，由于FPBH通過(guò)拓?fù)鋭澐诌M(jìn)行內(nèi)容鏡像分發(fā)，避免了鏡像過(guò)于集中，進(jìn)一步優(yōu)化了負(fù)載分布。

圖6 負(fù)載分布對(duì)比圖

綜合上述實(shí)驗(yàn)結(jié)果，本文提出的無(wú)線Mesh網(wǎng)絡(luò)中的四階段內(nèi)容鏡像分發(fā)方法FPBH在平均時(shí)延、網(wǎng)絡(luò)負(fù)載和負(fù)載分布性能上優(yōu)于現(xiàn)有的Mesh網(wǎng)絡(luò)中的其他分配方案。因此，F(xiàn)PBH方案可大大提高無(wú)線Mesh網(wǎng)絡(luò)的性能，滿足軍事信息網(wǎng)絡(luò)的內(nèi)容分發(fā)需求。

5 結(jié) 語(yǔ)

本文針對(duì)軍事信息系統(tǒng)中基于無(wú)線Mesh網(wǎng)絡(luò)的內(nèi)容分發(fā)問題，設(shè)計(jì)了立體化的軍事情報(bào)信息中心-戰(zhàn)術(shù)通信衛(wèi)星-小型分布式地面站-作戰(zhàn)單元網(wǎng)絡(luò)結(jié)構(gòu)模型。在此基礎(chǔ)上，提出了全新的分布式四階段啟發(fā)式算法。該方案根據(jù)各內(nèi)容對(duì)象的訂閱信息，統(tǒng)計(jì)各個(gè)內(nèi)容對(duì)象的熱度，并據(jù)此計(jì)算每個(gè)內(nèi)容對(duì)象所需的鏡像數(shù)目。對(duì)于所需鏡像數(shù)目為p的內(nèi)容對(duì)象，將地面站組成的網(wǎng)絡(luò)骨干進(jìn)行p劃分，在每個(gè)劃分中選擇一個(gè)鏡像分發(fā)位置。仿真實(shí)驗(yàn)證明，我們所提出的算法在平均時(shí)延，網(wǎng)絡(luò)負(fù)載和負(fù)載分布等方面上均有良好的性能，能夠極大地提高軍事信息系統(tǒng)中網(wǎng)絡(luò)資源受限場(chǎng)景下的服務(wù)質(zhì)量。

[1] 劉覓,彭木根,王文博. 基于IEEE802.16—2004標(biāo)準(zhǔn)的Mesh機(jī)制 [J]. 中國(guó)電子科學(xué)研究院學(xué)報(bào), 2006, 1(1): 75-80.

[2] Akyildiz I F, Wang X, Wang W. Wireless mesh networks: a survey [J]. Computer networks, 2005, 47(4): 445-487.

[3] Das S M, Pucha H, Hu Y C. Mitigating the gateway bottleneck via transparent cooperative caching in wireless mesh networks [J]. Ad Hoc Networks, 2007, 5(6): 680-703.

[4] Vakali A, Pallis G. Content delivery networks: Status and trends. Internet Computing, IEEE, 2003, 7(6):68-74.

[5] 馬曉亭.基于802.16d無(wú)線Mesh網(wǎng)絡(luò)的集團(tuán)軍戰(zhàn)役指揮所通信系統(tǒng)[J].電信快報(bào),2008, 10(10): 8-11.

[6] 劉顯靜,吳學(xué)智,何如龍等. 基于無(wú)線Mesh網(wǎng)絡(luò)的艦艇編隊(duì)通信網(wǎng)運(yùn)用研究[J]. 艦船電子工程, 2012, 32(6): 92-94.

[7] Jin S, Wang L. Content and service replication strategies in multi-hop wireless mesh networks [C]. Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, 2005: 79-86.

[8] Wang K, Chen Z, Liu H. Push-Based Wireless Converged Networks for Massive Multimedia Content Delivery [J]. IEEE Transactions on Wireless Communications, 2014, 13(5): 2894-2905.

[9] Johnston M, Lee H W, Modiano E. Robust network design for stochastic traffic demands [J]. Journal of Lightwave Technology, 2013, 31(18): 3104-3116.

[10] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs [J]. Bell system technical journal, 1970, 49(2): 291-307.

[11] Stoica I, Morris R, Liben-Nowell D, et al. Chord: A Scalabel Peer-to-Peer Lookup Protocol for Internet Applications [J]. IEEE/ACM Transactions on Networking, 2003, 11(1): 17-32.

[12] 吳劍鋒,郭英,范海寧. OMNeT++網(wǎng)絡(luò)仿真器的設(shè)計(jì)原理分析[J].微計(jì)算機(jī)應(yīng)用, 2008, 29(5): 34-37.

[13] Pallis G, Vakali A, Stamos K, et al. A latency-based object placement approach in content distribution networks[C]. IEEE Third Latin American Web Congress (LA-WEB), 2005: 1-8.