文吉?jiǎng)?，謝鯤，謝高崗，張廣興，李仁發(fā)

（1. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190；2. 湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙 410082）

1 引言

多跳無線mesh網(wǎng)絡(luò)(wireless mesh networks)作為一種動(dòng)態(tài)自組織、自配置的網(wǎng)絡(luò)，具有高度靈活性、健壯性、高帶寬、易維護(hù)等特點(diǎn)，可為用戶提供各種各樣的應(yīng)用，如寬帶家庭網(wǎng)絡(luò)、社區(qū)網(wǎng)絡(luò)、企業(yè)網(wǎng)絡(luò)，建筑自動(dòng)化等，并有望成為下一代無線接入網(wǎng)的標(biāo)準(zhǔn)技術(shù)[1～3]。

為提高無線網(wǎng)絡(luò)中的資源共享效率，加速資源下載速度，P2P技術(shù)以其網(wǎng)絡(luò)帶寬利用率高、下載速度快等特點(diǎn)，已經(jīng)越來越被研究人員重視并應(yīng)用到無線網(wǎng)絡(luò)中?，F(xiàn)有的無線網(wǎng)絡(luò)P2P技術(shù)研究主要集中在如何發(fā)現(xiàn)節(jié)點(diǎn)及如何選擇提供下載服務(wù)節(jié)點(diǎn)以降低資源的下載時(shí)間。相對(duì)于有線網(wǎng)絡(luò)而言，多跳無線mesh網(wǎng)絡(luò)具有有限的帶寬和多跳轉(zhuǎn)發(fā)的復(fù)雜無線環(huán)境，在進(jìn)行P2P資源管理中存在如下挑戰(zhàn)。

1) 傳統(tǒng)P2P資源共享方式中，每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)都是同等地對(duì)待，以形成資源共享P2P覆蓋網(wǎng)結(jié)構(gòu)。然而，多跳無線mesh網(wǎng)絡(luò)由2種節(jié)點(diǎn)組成，mesh路由器節(jié)點(diǎn)(mesh router)和移動(dòng)客戶端節(jié)點(diǎn) (mobile client)，如圖1所示。mesh路由器通常具有2種基本功能，作為mesh網(wǎng)絡(luò)的骨干鏈路，完成數(shù)據(jù)分組的轉(zhuǎn)發(fā)功能；作為移動(dòng)客戶端的接入節(jié)點(diǎn)(access point)，負(fù)責(zé)移動(dòng)客戶端的網(wǎng)絡(luò)接入。若在多跳無線mesh網(wǎng)絡(luò)中仍然采用傳統(tǒng)的方式，不對(duì)mesh路由器節(jié)點(diǎn)和移動(dòng)客戶端節(jié)點(diǎn)進(jìn)行區(qū)分，而是均等地對(duì)待每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)來組建P2P覆蓋網(wǎng)絡(luò)，將會(huì)產(chǎn)生極大的帶寬浪費(fèi)。

圖1 多跳無線mesh網(wǎng)絡(luò)結(jié)構(gòu)

2) 在多跳無線mesh網(wǎng)絡(luò)中，mesh路由器節(jié)點(diǎn)通過無線鏈路自動(dòng)建立和維護(hù)相互之間的連接。移動(dòng)客戶端節(jié)點(diǎn)通過mesh路由器節(jié)點(diǎn)的接入服務(wù)實(shí)現(xiàn)互連互通。連接在同一個(gè)mesh路由器節(jié)點(diǎn)上的多個(gè)移動(dòng)客戶端節(jié)點(diǎn)進(jìn)行資源的上傳和下載時(shí)，所有的數(shù)據(jù)分組都是通過mesh路由器進(jìn)行轉(zhuǎn)發(fā)，且通過競(jìng)爭(zhēng)的方式獲得mesh路由器的上傳和下載帶寬。如果不考慮這種物理上的連接關(guān)系，仍然采用傳統(tǒng)的方式組建P2P覆蓋網(wǎng)絡(luò)，將使得無線mesh網(wǎng)絡(luò)的物理拓?fù)浜蚉2P覆蓋網(wǎng)的邏輯拓?fù)鋰?yán)重不一致，從而降低P2P資源共享的效率。

3) 多跳無線mesh網(wǎng)絡(luò)中，mesh路由器一經(jīng)部署，一般處于準(zhǔn)靜止的狀態(tài)。與mesh路由器節(jié)點(diǎn)不同的是，移動(dòng)客戶端節(jié)點(diǎn)通常具有有限的能量和高度的移動(dòng)性。使用移動(dòng)客戶端作為資源傳輸源節(jié)點(diǎn)時(shí)，移動(dòng)客戶端在無線mesh網(wǎng)絡(luò)中移動(dòng)會(huì)產(chǎn)生網(wǎng)絡(luò)切換，切換的延時(shí)可能會(huì)導(dǎo)致資源下載的中斷，引起資源傳輸路由的不穩(wěn)定，最終會(huì)嚴(yán)重影響P2P應(yīng)用的性能（如P2P流媒體傳輸）。

因此，設(shè)計(jì)多跳無線mesh網(wǎng)絡(luò)中的P2P結(jié)構(gòu)、資源檢索和分發(fā)協(xié)議時(shí)，需要將無線mesh網(wǎng)的拓?fù)浣Y(jié)構(gòu)特點(diǎn)和移動(dòng)客戶端的移動(dòng)性作為重要因素進(jìn)行考慮，以提高資源下載的穩(wěn)定性，降低資源下載的延時(shí)和中斷。為了解決上述挑戰(zhàn)，本文提出了一種基于分簇P2P的多跳無線mesh網(wǎng)絡(luò)資源密度敏感的資源檢索和分發(fā)算法。為有效利用多跳無線mesh網(wǎng)絡(luò)的無線資源，根據(jù)無線mesh網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)和不同類型節(jié)點(diǎn)的特征，將多跳無線mesh網(wǎng)絡(luò)建模成分簇P2P結(jié)構(gòu)；為了降低資源發(fā)布的開銷，使用結(jié)構(gòu)精簡(jiǎn)的布魯姆過濾器作為資源表示的數(shù)據(jù)結(jié)構(gòu)，并作為消息在無線網(wǎng)絡(luò)中傳輸；為了提高資源下載服務(wù)的穩(wěn)定性，提出了資源密度敏感的資源檢索和分發(fā)算法。在進(jìn)行資源檢索時(shí)，將無線網(wǎng)絡(luò)中移動(dòng)客戶端的資源下載請(qǐng)求轉(zhuǎn)發(fā)到擁有資源副本最多的P2P分簇中；在進(jìn)行資源分發(fā)時(shí)，利用簇頭的協(xié)調(diào)能力，當(dāng)節(jié)點(diǎn)移動(dòng)時(shí)選擇本簇內(nèi)的副本節(jié)點(diǎn)繼續(xù)提供下載服務(wù)，最大程度地降低由于節(jié)點(diǎn)的移動(dòng)性而產(chǎn)生的資源下載中斷和下載的不穩(wěn)定性。

2 相關(guān)工作

在無線網(wǎng)絡(luò)中研究P2P分發(fā)技術(shù)，成為P2P技術(shù)研究的新的挑戰(zhàn)和熱點(diǎn)。如文獻(xiàn)[4]中提出了一種面向擁塞失真優(yōu)化分布式的速率分配框架，該框架是一種基于聯(lián)合媒體敏感和網(wǎng)絡(luò)敏感的跨層資源分配框架。文獻(xiàn)[5]中提出了一種在無線多跳網(wǎng)絡(luò)中的基于價(jià)格的公平速率分配算法，該算法基于MAC層的時(shí)間限制在動(dòng)態(tài)無線網(wǎng)絡(luò)中進(jìn)行公平的速率分配。文獻(xiàn)[6]中聯(lián)合網(wǎng)絡(luò)編碼研究多播樹的資源分配問題。文獻(xiàn)[7]提出一種接受者驅(qū)動(dòng)的分發(fā)框架，在這個(gè)框架中進(jìn)行數(shù)據(jù)分發(fā)時(shí)分為2輪，首先新的內(nèi)容在全網(wǎng)范圍內(nèi)迅速地?cái)U(kuò)散，然后節(jié)點(diǎn)之間再交換所需的信息。

為了降低P2P中消息傳輸開銷，學(xué)者們提出了一種超級(jí)節(jié)點(diǎn)的P2P網(wǎng)絡(luò)結(jié)構(gòu)，對(duì)節(jié)點(diǎn)分簇來改善P2P的組織結(jié)構(gòu)[8～10]。在該網(wǎng)絡(luò)中的一組節(jié)點(diǎn)構(gòu)成一個(gè)節(jié)點(diǎn)簇，超級(jí)節(jié)點(diǎn)簇頭負(fù)責(zé)管理它內(nèi)部的多個(gè)節(jié)點(diǎn)的通信。通過這種分簇的方式，整個(gè)P2P網(wǎng)絡(luò)的管理就分散到各個(gè)超級(jí)節(jié)點(diǎn)，網(wǎng)絡(luò)整體性能得到了明顯的提升[8,11～13]。文獻(xiàn)[14]表明基于物理網(wǎng)絡(luò)臨近節(jié)點(diǎn)構(gòu)造分簇P2P覆蓋網(wǎng)可以大大提高消息的傳輸性能。在資源共享的應(yīng)用中，將共享相似資源的節(jié)點(diǎn)劃分為一個(gè)分簇。這樣在處理資源查詢請(qǐng)求時(shí)，通過將資源下載請(qǐng)求消息路由到相對(duì)應(yīng)的分簇，在簇內(nèi)完成深度的內(nèi)容檢索，提高資源檢索的性能[14～16]。文獻(xiàn)[17]利用分簇網(wǎng)絡(luò)中的低簇間網(wǎng)絡(luò)延時(shí)的特性，將并行程序的各個(gè)并行部分分散到簇內(nèi)的多個(gè)站點(diǎn)執(zhí)行[18]。

與現(xiàn)有分簇P2P類似的是，在進(jìn)行多跳無線mesh網(wǎng)絡(luò)建模時(shí)，直接利用多跳無線mesh網(wǎng)絡(luò)的特點(diǎn)，將物理網(wǎng)絡(luò)臨近的節(jié)點(diǎn)構(gòu)造成P2P分簇。不同的是，為了有效利用無線網(wǎng)絡(luò)資源和無線mesh網(wǎng)絡(luò)中的上下行帶寬，通過區(qū)分對(duì)待無線mesh網(wǎng)絡(luò)的節(jié)點(diǎn)，直接將無線mesh 路由器和與之關(guān)聯(lián)的移動(dòng)客戶端節(jié)點(diǎn)分為一個(gè)資源共享簇。

3 網(wǎng)絡(luò)模型和問題描述

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

首先，將多跳無線 mesh網(wǎng)絡(luò)建模為分簇P2P結(jié)構(gòu)。相對(duì)于移動(dòng)客戶端節(jié)點(diǎn)而言，mesh路由器節(jié)點(diǎn)通常處于有源的靜止?fàn)顟B(tài)，且具有更高的處理能力、帶寬和能量。因此，在選擇簇頭時(shí)，使用mesh路由器節(jié)點(diǎn)作為簇頭。本文所設(shè)計(jì)的分簇P2P在資源檢索和控制層面上采用2層設(shè)計(jì)，如圖2所示。一層是由 mesh路由器節(jié)點(diǎn)組成的有結(jié)構(gòu)網(wǎng)絡(luò)，另一層是由移動(dòng)客戶節(jié)點(diǎn)組成的無結(jié)構(gòu)P2P 網(wǎng)絡(luò)。整個(gè) mesh網(wǎng)絡(luò)被分成多個(gè)區(qū)域。每簇包含一個(gè)無線mesh路由器節(jié)點(diǎn)和若干個(gè)與之相關(guān)聯(lián)的移動(dòng)客戶端節(jié)點(diǎn)。移動(dòng)客戶端節(jié)點(diǎn)只與簇頭 mesh路由器節(jié)點(diǎn)通信，簇頭與簇頭構(gòu)成高一級(jí)的虛擬骨干網(wǎng)，負(fù)責(zé)簇內(nèi)的數(shù)據(jù)融合和簇間數(shù)據(jù)轉(zhuǎn)發(fā)。

更進(jìn)一步，用G = (V,E)表示無線mesh網(wǎng)絡(luò)。其中，V表示節(jié)點(diǎn)集合，E表示邊的集合。任意的節(jié)點(diǎn) v∈V表示無線 mesh網(wǎng)絡(luò)中的實(shí)際網(wǎng)絡(luò)節(jié)點(diǎn)（包括mesh路由器節(jié)點(diǎn)集合Vr和移動(dòng)客戶端節(jié)點(diǎn)結(jié)合Vc）。對(duì)于任何節(jié)點(diǎn)u和v∈Vr，若2節(jié)點(diǎn)可以通過無線鏈路直接進(jìn)行通信，則存在邊edge (u, v)∈E。整個(gè)無線網(wǎng)絡(luò)由多個(gè)分簇組成{V1, V2, V3,…,Vk}。每個(gè)簇由一個(gè)無線mesh路由器和與之關(guān)聯(lián)的移動(dòng)客戶端節(jié)點(diǎn)構(gòu)成，即Vi={vi，所有與Vi關(guān)聯(lián)移動(dòng)客戶端，且 u∈Vc，Vi∈Vr}。

圖2 基于分簇的多跳無線mesh網(wǎng)絡(luò)建模

與現(xiàn)有的802.11無線網(wǎng)絡(luò)協(xié)議相一致，假設(shè)移動(dòng)客戶端節(jié)點(diǎn)與 mesh路由器為單連接關(guān)系，即每個(gè)移動(dòng)客戶端在同一時(shí)刻能且僅能和一個(gè) mesh路由器關(guān)聯(lián)。即使移動(dòng)客戶端在多個(gè) mesh路由器的覆蓋范圍內(nèi)，每個(gè)移動(dòng)客戶端也只能與一個(gè)無線mesh路由器關(guān)聯(lián)。那么多跳無線mesh網(wǎng)絡(luò)的分簇P2P 結(jié)構(gòu){V1, V2, V3,…, Vk}(Vi?V, 1≤i≤k) 其實(shí)是G的一個(gè)覆蓋，滿足條件 V1∪V2∪V3∪…∪Vk= V且 Vi∩ Vj=φ(1≤i＜j≤k)。每個(gè) mesh 路由器節(jié)點(diǎn)負(fù)責(zé)該簇資源的管理，每個(gè)移動(dòng)客戶端節(jié)點(diǎn)組成分簇P2P結(jié)構(gòu)中的節(jié)點(diǎn)。本文將基于分簇P2P結(jié)構(gòu)實(shí)現(xiàn)無線mesh網(wǎng)絡(luò)中的資源共享和傳輸優(yōu)化。

移動(dòng)客戶端節(jié)點(diǎn)可以是使用iOS、Android系統(tǒng)等智能終端、筆記本等多種上網(wǎng)設(shè)備，它們通過與之關(guān)聯(lián)的 mesh路由器從無線 mesh網(wǎng)絡(luò)下載資源。將無線 mesh網(wǎng)絡(luò)設(shè)計(jì)為分簇P2P結(jié)構(gòu)是為了利用多跳無線 mesh網(wǎng)絡(luò)中內(nèi)部擁有的資源實(shí)現(xiàn)資源共享。

3.2 問題描述

在多跳無線mesh網(wǎng)絡(luò)進(jìn)行P2P資源管理有2個(gè)方面的特點(diǎn)。

一方面，副本的存在是提高P2P 系統(tǒng)的可擴(kuò)展性、容錯(cuò)性、可用性和減少查詢響應(yīng)時(shí)間的有效手段。因?yàn)槎鄠€(gè)移動(dòng)客戶端節(jié)點(diǎn)存儲(chǔ)了資源的多個(gè)副本，所以使用分簇P2P來建模無線mesh網(wǎng)絡(luò)時(shí)，每個(gè)簇下可能有多個(gè)副本。另一方面，在無線mesh網(wǎng)絡(luò)中部署P2P，移動(dòng)客戶端節(jié)點(diǎn)具有有限的能量和高度移動(dòng)性。要提高無線 mesh網(wǎng)絡(luò)中資源查找效率，就必須考慮到移動(dòng)終端節(jié)點(diǎn)的移動(dòng)性，降低由于節(jié)點(diǎn)移動(dòng)而帶來的資源下載中斷和不穩(wěn)定性。

為解決多跳無線 mesh網(wǎng)絡(luò)中高效資源檢索的問題，利用多副本帶來的高容錯(cuò)性和可用性，將資源下載請(qǐng)求消息直接發(fā)送到資源密度最大的分簇，利用簇內(nèi)擁有多個(gè)資源副本備份為請(qǐng)求節(jié)點(diǎn)提供持續(xù)的資源下載服務(wù)，可以最大化降低由于節(jié)點(diǎn)移動(dòng)性時(shí)網(wǎng)絡(luò)切換而帶來的資源下載中斷，并減少由于重新路由而帶來的資源下載不穩(wěn)定性。設(shè)定G =(V,E)和資源下載請(qǐng)求的移動(dòng)客戶端節(jié)點(diǎn)iv′∈Vc，找一條連接資源最密集分簇簇頭的資源下載路徑P(P連接Vi和Vj，其中，Vi是iv′的super-node節(jié)點(diǎn)，Vj是擁有最多所請(qǐng)求資源副本的簇頭)，然后利用 Vj中的多個(gè)資源備份為iv′提供下載服務(wù)。本文稱該問題為資源密度敏感的資源檢索和分發(fā)問題。

4 基于Bloom filter的P2P資源管理

在進(jìn)行資源管理時(shí)，為了資源檢索方便，每個(gè)移動(dòng)客戶端節(jié)點(diǎn)定期將自己存儲(chǔ)的資源索引傳輸給本簇的簇頭，簇頭存儲(chǔ)其所對(duì)應(yīng)簇的全部資源索引信息。因此，在分簇P2P實(shí)現(xiàn)資源的查找和管理時(shí)，首先需要設(shè)計(jì)對(duì)應(yīng)的資源檢索數(shù)據(jù)結(jié)構(gòu)，用以表示資源信息并作為消息在多跳無線mesh網(wǎng)絡(luò)中傳遞。

由于所設(shè)計(jì)的資源索引數(shù)據(jù)結(jié)構(gòu)需要在無線mesh網(wǎng)絡(luò)傳輸，所以數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)應(yīng)該考慮如下幾個(gè)因素：1）相比于有線網(wǎng)絡(luò)，無線網(wǎng)絡(luò)的帶寬資源有限，因此用于表示和傳輸資源存儲(chǔ)信息的數(shù)據(jù)結(jié)構(gòu)必須是簡(jiǎn)潔的。2）因?yàn)闊o線網(wǎng)絡(luò)的數(shù)據(jù)傳輸是廣播形式，數(shù)據(jù)在無線網(wǎng)絡(luò)極易被偵聽，因此，為了安全考慮，表示資源存儲(chǔ)信息的數(shù)據(jù)結(jié)構(gòu)必須是保護(hù)隱私的。

由于布魯姆過濾器是一種精簡(jiǎn)的信息表示方案，它在數(shù)據(jù)庫(kù)、覆蓋網(wǎng)和P2P網(wǎng)節(jié)點(diǎn)協(xié)作交互、資源路由、數(shù)據(jù)幀路由標(biāo)簽、網(wǎng)絡(luò)測(cè)量管理、網(wǎng)絡(luò)入侵檢測(cè)、無線網(wǎng)絡(luò)交互協(xié)議設(shè)計(jì)、流數(shù)據(jù)管理等方面具有廣泛的應(yīng)用[19]，因此，本文使用布魯姆過濾器作為資源索引的數(shù)據(jù)結(jié)構(gòu)。

布魯姆過濾器對(duì)集合采用一個(gè)位串表示并能有效支持元素的散列查找，它對(duì)每個(gè)元素的表示只需要幾個(gè)比特，是一種能夠表示集合、支持集合查詢的簡(jiǎn)潔數(shù)據(jù)結(jié)構(gòu)。布魯姆過濾器查詢算法核心是一個(gè)V向量和一組散列函數(shù)。設(shè)集合S={s1,s2,…,sn}共有n個(gè)元素，通過k個(gè)散列函數(shù)h1,h2,…,hk映射到長(zhǎng)度為m的向量V中。通常說布魯姆過濾器表示匯總信息(summary)就是指這個(gè)向量 V，這里的 V向量用BF表示。每一個(gè)散列函數(shù)相互獨(dú)立且函數(shù)的取值范圍為{0,1,2,…,m-1}。集合映射到過濾器時(shí)，首先將向量V初始化，將向量V所有bit位置0。當(dāng)元素插入集合中時(shí)，對(duì)于每一個(gè)元素si，計(jì)算hj(si)(1≤j≤k)，若 hj(si)=q，則令 BF[q]=1，將向量對(duì)應(yīng)位置置位，完成元素的插入。向量中任何一個(gè)位置可能會(huì)多次置位，但僅第一次置位有效；當(dāng)查詢?cè)厥欠裨诩蠒r(shí)，對(duì)于給定的元素 x，檢查向量V的k個(gè)位置(h1(x),h2(x),…,hk(x))是否都為1。如果有一個(gè)為0，x一定不在集合中;如果全是1，x可能在集合中，也可能不在集合中。此時(shí)就可能出現(xiàn)所謂假陽(yáng)性誤判(false positive)，即將不屬于集合的元素誤判斷成屬于集合中，而不存在假陰性誤判(false negative)，即永遠(yuǎn)不會(huì)將屬于集合中的元素誤判為不屬于集合中。

傳統(tǒng)的樹型查詢算法和散列查詢算法存儲(chǔ)空間與元素自身大小及集合規(guī)模直接相關(guān)，而布魯姆過濾器查詢算法所需空間與元素自身的大小無關(guān)，僅僅與元素映射到向量的位數(shù)相關(guān)，使用m比特的空間表示 n個(gè)元素的集合，每個(gè)元素平均只需要 m/n比特位，大大節(jié)約存儲(chǔ)空間?？梢钥闯觯剪斈愤^濾器是一種允許存在一定誤判的情況下，減少存儲(chǔ)空間的散列結(jié)構(gòu)，是查詢準(zhǔn)確率和存儲(chǔ)代價(jià)的折衷。

移動(dòng)客戶端節(jié)點(diǎn)定期向簇頭（mesh路由器節(jié)點(diǎn)）發(fā)布其存儲(chǔ)的資源。在具體的實(shí)現(xiàn)中，可以假設(shè)每個(gè)資源都有對(duì)應(yīng)的資源名稱，以這一名稱為依據(jù)制定散列函數(shù)，并以資源名稱作為布魯姆過濾器生成散列映射地址的依據(jù)，將每個(gè)資源在布魯姆過濾器中對(duì)應(yīng)的k個(gè)bit位置位，具體操作如圖3所示。

圖3 移動(dòng)客戶端節(jié)點(diǎn)的資源索引建立

移動(dòng)客戶端向簇頭發(fā)布其存儲(chǔ)的資源時(shí)，將m比特長(zhǎng)的布魯姆過濾器向量傳輸給簇頭。當(dāng)移動(dòng)客戶端節(jié)點(diǎn)向?qū)?yīng)的簇頭登記存儲(chǔ)的資源信息后，每個(gè)簇頭都緩存著該簇范圍內(nèi)的移動(dòng)客戶端節(jié)點(diǎn)的資源目錄摘要信息，這些信息都是用布魯姆過濾器表示的。多個(gè)移動(dòng)客戶端節(jié)點(diǎn)的資源目錄摘要信息在簇頭中形成布魯姆過濾器01矩陣，如圖4所示。

圖4 簇頭存儲(chǔ)的多個(gè)移動(dòng)客戶端資源索引矩陣

當(dāng)移動(dòng)客戶端節(jié)點(diǎn)移出 mesh路由器的覆蓋范圍時(shí)，移動(dòng)客戶端就會(huì)發(fā)生網(wǎng)絡(luò)切換（即將網(wǎng)絡(luò)關(guān)聯(lián)關(guān)系從一個(gè) mesh路由器轉(zhuǎn)到另一個(gè) mesh路由器）。此時(shí)移動(dòng)客戶端需要向新關(guān)聯(lián)的簇頭發(fā)布資源，即傳輸布魯姆過濾器位給該簇頭mesh路由器，同時(shí)向之前關(guān)聯(lián)的簇頭撤銷資源，即向之前關(guān)聯(lián)的mesh路由器通知之前的布魯姆過濾器不可用（具體操作可見刪除索引矩陣的對(duì)應(yīng)行向量）。

5 基于資源密度的資源檢索和分發(fā)算法

本文的目的是給定資源請(qǐng)求的移動(dòng)客戶端節(jié)點(diǎn)vi′ ∈Vc，找到一條連接資源最密集簇頭的路徑，保證其資源下載的穩(wěn)定性和連續(xù)性，減少資源消耗并提高下載吞吐量。要找到一條從移動(dòng)客戶端節(jié)點(diǎn)到資源最密集簇的簇頭，首先必須在簇頭對(duì)所請(qǐng)求資源進(jìn)行資源密度評(píng)估，統(tǒng)計(jì)每個(gè)簇的資源分布情況。

因?yàn)榇仡^資源矩陣中每一行都表示一個(gè)移動(dòng)客戶端節(jié)點(diǎn)存儲(chǔ)的資源索引，針對(duì)關(guān)鍵字為key1的資源檢索過程就可以采用類似于柵格掃描的形式，如圖5的陰影表示，如果每一行中柵格位的bit位之和等于k，

圖5 基于布魯姆過濾器的資源密度估計(jì)

則表明對(duì)應(yīng)的移動(dòng)客戶端節(jié)點(diǎn)有需要請(qǐng)求的資源，否則沒有對(duì)應(yīng)的資源。

統(tǒng)計(jì)所有等于k的柵格行數(shù)，可得該簇中擁有請(qǐng)求資源的移動(dòng)客戶端數(shù)目。定義一個(gè)簇中擁有請(qǐng)求資源的移動(dòng)客戶端數(shù)目為資源密度d。

提出的基于資源密度的資源檢索算法分為3個(gè)步驟，如下所示。

算法1 基于資源密度的可靠資源檢索算法

Step1 移動(dòng)客戶端節(jié)點(diǎn) c將需要請(qǐng)求的資源通過其關(guān)聯(lián)的路由器節(jié)點(diǎn)r向TTL范圍內(nèi)的mesh路由器廣播。

Step2 收到廣播請(qǐng)求的路由器節(jié)點(diǎn)評(píng)估所管理的簇資源密度，其過程如下：

初始化資源密度為d=0；

利用 k個(gè)散列函數(shù)將所請(qǐng)求的資源關(guān)鍵字key計(jì)算，在對(duì)應(yīng)的布魯姆過濾器矩陣的k個(gè)柵格位置進(jìn)行掃描；評(píng)估完資源密度后，每個(gè) mesh路由器將自己簇中所擁有的資源密度告訴mesh路由器r。

Step3 mesh路由器r比較TTL范圍內(nèi)相鄰的多個(gè)路由器的資源密度，選擇資源密度最大的簇，當(dāng)多個(gè)分簇具有相同的資源密度時(shí)，選擇最近的分簇為資源請(qǐng)求發(fā)送分簇。

Step4 運(yùn)行最短路徑算法，將資源下載請(qǐng)求消息路由到資源密度最大的那個(gè)分簇。

當(dāng)移動(dòng)客戶端在進(jìn)行資源檢索時(shí)，首先將需要請(qǐng)求的資源名通過其對(duì)應(yīng)的 mesh路由器在多跳無線mesh網(wǎng)絡(luò)中廣播。然后每個(gè)TTL范圍內(nèi)的mesh路由器首先評(píng)估所對(duì)應(yīng)分簇的資源密度，即獲得本簇內(nèi)移動(dòng)客戶端節(jié)點(diǎn)擁有所請(qǐng)求的資源數(shù)量。最后將資源檢索請(qǐng)求發(fā)送到資源密度最大的分簇。這樣，即使擁有資源的某個(gè)移動(dòng)客戶端節(jié)點(diǎn)移動(dòng)或斷電等其他因素導(dǎo)致暫時(shí)無法提供資源下載服務(wù)，由于資源下載請(qǐng)求發(fā)送到了資源密度最大的那個(gè)分簇，所請(qǐng)求資源還是可以從該簇其他擁有資源的節(jié)點(diǎn)穩(wěn)定地傳送給該移動(dòng)客戶端。

基于所提出的資源密度檢索算法，提出備份節(jié)點(diǎn)分發(fā)算法。具體思想是基于 mesh路由器作為簇頭的協(xié)調(diào)能力，利用該分簇的多個(gè)資源副本備份提供資源下載服務(wù)，以最大化降低由于節(jié)點(diǎn)移動(dòng)性而產(chǎn)生的資源下載中斷。當(dāng)提供資源下載的節(jié)點(diǎn) c1由于移動(dòng)而移出所對(duì)應(yīng)的mesh路由器r的覆蓋范圍時(shí)，由mesh路由器r指定該簇中另外一個(gè)擁有資源的移動(dòng)客戶端節(jié)點(diǎn)c備給c提供資源下載服務(wù)。該過程一直持續(xù)下去，直至該簇再也沒有可以提供資源的移動(dòng)客戶端節(jié)點(diǎn)，否則一直由該簇為c提供資源下載服務(wù)。在簇頭進(jìn)行備份節(jié)點(diǎn)選擇時(shí)，可以綜合考慮節(jié)點(diǎn)能量E、帶寬B和節(jié)點(diǎn)自身能力C等多種因素。在設(shè)計(jì)中定義 Fun(i)=αE+βB+λC 為 i節(jié)點(diǎn)作為備份節(jié)點(diǎn)的能力，選擇Fun(i)最大的i節(jié)點(diǎn)作為備份節(jié)點(diǎn)提供資源下載服務(wù)，以最大化P2P下載性能。

為了提供移動(dòng)環(huán)境中持續(xù)的資源下載服務(wù)，本文提出的資源檢索和分發(fā)算法可采用 Mobile IP來提供持續(xù)的服務(wù)。Mesh路由器作為Mobile IP中的家鄉(xiāng)代理和外部代理，節(jié)點(diǎn)的移動(dòng)性都需要向mesh路由器發(fā)布位置更新和移動(dòng)更新。管理移動(dòng)性的具體流程如下：當(dāng)資源請(qǐng)求節(jié)點(diǎn)移動(dòng)時(shí)，需要向之前的家鄉(xiāng)代理 mesh路由器發(fā)布mobile IP的更新和綁定消息，從而確保數(shù)據(jù)源節(jié)點(diǎn)和該節(jié)點(diǎn)的持續(xù)通信。當(dāng)數(shù)據(jù)源節(jié)點(diǎn)移動(dòng)時(shí)，則由該源節(jié)點(diǎn)對(duì)應(yīng)的mesh路由器節(jié)點(diǎn)指定備份節(jié)點(diǎn)提供資源服務(wù)，所有與目的移動(dòng)節(jié)點(diǎn)的通信數(shù)據(jù)都需要由該mesh路由器節(jié)點(diǎn)正確地轉(zhuǎn)發(fā)到備份節(jié)點(diǎn)。

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

仿真實(shí)驗(yàn)實(shí)現(xiàn)了3種資源檢索和2種資源分發(fā)機(jī)制。其中，所實(shí)現(xiàn)的資源檢索機(jī)制包括：

1) 本文所提出的資源密度敏感的資源檢索機(jī)制（density）。在進(jìn)行請(qǐng)求消息發(fā)送和確定服務(wù)mesh路由器節(jié)點(diǎn)的過程中，需要進(jìn)行資源下載的移動(dòng)客戶端 C1將資源下載請(qǐng)求消息發(fā)送到資源最密集簇的mesh路由器節(jié)點(diǎn)R1，由R1協(xié)調(diào)并指定本簇中的移動(dòng)客戶端節(jié)點(diǎn)為 C1提供資源傳輸服務(wù)；2) 隨機(jī)資源檢索（random）。C1的資源請(qǐng)求消息會(huì)隨機(jī)地發(fā)送給任意一個(gè)擁有請(qǐng)求資源的mesh路由器R2，由R2協(xié)調(diào)并指定本簇中的移動(dòng)客戶端為C1提供資源傳輸服務(wù)；3) 最近資源檢索（near）。C1的資源請(qǐng)求消息會(huì)發(fā)送給最近的擁有請(qǐng)求資源的 mesh路由器 R3，由 R3協(xié)調(diào)并指定本簇中的移動(dòng)客戶端為C1提供資源傳輸服務(wù)。

所實(shí)現(xiàn)的資源分發(fā)機(jī)制包括：1) 副本備份節(jié)點(diǎn)分發(fā)機(jī)制（replica）。當(dāng)提供資源下載的節(jié)點(diǎn)C由于移動(dòng)而移出所對(duì)應(yīng)的mesh路由器R的信號(hào)覆蓋范圍時(shí)，由R指定該簇中另外一個(gè)擁有資源的移動(dòng)客戶端節(jié)點(diǎn)C備給C1提供資源下載服務(wù)。該過程一直持續(xù)下去，直至R下沒有可以提供資源的移動(dòng)客戶端節(jié)點(diǎn)，否則一直由R所在分簇為C1提供資源下載服務(wù)。2) 移動(dòng)節(jié)點(diǎn)分發(fā)機(jī)制（mobile）。當(dāng)提供資源下載的節(jié)點(diǎn)C由于移動(dòng)而移出所對(duì)應(yīng)的mesh路由器R的信號(hào)覆蓋范圍時(shí)，C會(huì)自動(dòng)選擇mesh網(wǎng)絡(luò)中信號(hào)最強(qiáng)的 mesh路由器連接，完成網(wǎng)絡(luò)切換獲得重新連接后繼續(xù)給C1提供服務(wù)。

將上述3種資源檢索機(jī)制和2種資源分發(fā)機(jī)制進(jìn)行組合，在仿真實(shí)驗(yàn)中共實(shí)現(xiàn)了6種資源檢索和分發(fā)算法。分別標(biāo)識(shí)為：Density_Replica, Random_Replica, Near_Replica, Density_Mobile, Random_Mobile, Near_Mobile。

仿真平臺(tái)為NCTUns[20]。如圖6所示，由一個(gè)6×6的mesh 路由器組成的多跳無線mesh網(wǎng)絡(luò)，其中，mesh路由器用M進(jìn)行標(biāo)記，移動(dòng)客戶端用b進(jìn)行標(biāo)記。在NCTUns中將這些mesh路由器都設(shè)置在一個(gè)子網(wǎng)里。每個(gè)mesh router有2個(gè)radio，另一個(gè)radio用于和其他mesh router進(jìn)行通信，一個(gè)radio用于提供移動(dòng)客戶端的AP訪問點(diǎn)的服務(wù)。在實(shí)驗(yàn)原型圖6中，移動(dòng)客戶端節(jié)點(diǎn)53作為資源的下載節(jié)點(diǎn)。

圖6 無線mesh網(wǎng)絡(luò)仿真環(huán)境

本文分別實(shí)現(xiàn)了6種檢索機(jī)制和分發(fā)機(jī)制的組合實(shí)驗(yàn)。其中，在仿真試驗(yàn)的Density_Replica機(jī)制中，節(jié)點(diǎn)53向資源密度最大的21號(hào)mesh路由器索取資源。由于采用備份節(jié)點(diǎn)分發(fā)的機(jī)制，移動(dòng)客戶端節(jié)點(diǎn) 41,40,39,38 分別在[0～20]，[20～40]，[40～60]，[60～80]s提供資源的下載服務(wù)。Random_Replica機(jī)制中，節(jié)點(diǎn)53向11號(hào)mesh 路由器索取資源。11號(hào)mesh路由器的移動(dòng)客戶端節(jié)點(diǎn)44,49,47在[0～25],[25～53],[53～80]s 提供資源的下載服務(wù)。Near_Replica機(jī)制中，節(jié)點(diǎn)53首先選取21號(hào)mesh路由器索取資源，然后向較近的8,23號(hào)mesh 路由器索取資源，移動(dòng)客戶端節(jié)點(diǎn) 41,42,47在[0～25],[25～53], [53～80]s提供資源的下載服務(wù)。Density_Mobile機(jī)制中，節(jié)點(diǎn)53向21號(hào)mesh 路由器索取資源。移動(dòng)節(jié)點(diǎn)41在[0～80]s提供資源的下載服務(wù)，同時(shí)節(jié)點(diǎn) 41在向 mesh路由器 6號(hào)節(jié)點(diǎn)移動(dòng)。Random_Mobile機(jī)制中，節(jié)點(diǎn)53向11號(hào)mesh 路由器索取資源，移動(dòng)客戶端節(jié)點(diǎn)44在[0～80]s提供資源的下載服務(wù)，與此同時(shí)，該移動(dòng)客戶端節(jié)點(diǎn)44向mesh 路由器36號(hào)節(jié)點(diǎn)移動(dòng)。Near_ Mobile機(jī)制中，節(jié)點(diǎn)53向8號(hào)mesh 路由器索取資源，移動(dòng)客戶端節(jié)點(diǎn)41在[0～80]s提供資源的下載服務(wù)，且移動(dòng)客戶端節(jié)點(diǎn)41向mesh路由器6號(hào)節(jié)點(diǎn)移動(dòng)。

圖7 下載速率隨仿真時(shí)間的變化

圖 7為資源下載速率隨仿真時(shí)間的變化趨勢(shì)圖。在圖7中，每個(gè)實(shí)驗(yàn)的頭10s進(jìn)行的是仿真初始化。為了更好地衡量資源下載的性能，表1列出從11～80s各種機(jī)制下的資源下載速率均值。為了反映實(shí)驗(yàn)結(jié)果相對(duì)于平均值(mean)的離散程度，以評(píng)估資源傳輸下載的穩(wěn)定性，表1還列出從11～80s各種機(jī)制下的資源下載速率的標(biāo)準(zhǔn)差。

對(duì)比相同資源檢索機(jī)制下的不同資源分發(fā)機(jī)制。對(duì)比Density_replica和Density_Mobile 2種資源分發(fā)機(jī)制。發(fā)現(xiàn)在Density_replica機(jī)制中，下載速率維持在一個(gè)穩(wěn)定水平，標(biāo)準(zhǔn)差最小，而Density_Mobile出現(xiàn)了下載速率為0的點(diǎn)，且下載速率標(biāo)準(zhǔn)差較大。這是因?yàn)閭鹘y(tǒng)的移動(dòng)節(jié)點(diǎn)的分發(fā)機(jī)制中，當(dāng)節(jié)點(diǎn)移動(dòng)跳出當(dāng)前 mesh路由器的覆蓋范圍時(shí)，移動(dòng)節(jié)點(diǎn)首先會(huì)掃描周圍的 mesh路由器節(jié)點(diǎn)，然后斷開 mesh路由器節(jié)點(diǎn)，并選擇信號(hào)最強(qiáng)的 mesh路由器節(jié)點(diǎn)進(jìn)行重新關(guān)聯(lián)，完成網(wǎng)絡(luò)的切換。由于重新關(guān)聯(lián)的切換延時(shí)會(huì)使得傳統(tǒng)的移動(dòng)節(jié)點(diǎn)分發(fā)機(jī)制出現(xiàn)下載速率為0的現(xiàn)象。除此之外，Density_Mobile下載速率波動(dòng)較大的另一個(gè)原因是移動(dòng)客戶端重新關(guān)聯(lián)了 mesh路由器，導(dǎo)致下載路由路徑也發(fā)生變化。

表1 平均下載速率和標(biāo)準(zhǔn)差

對(duì)比不同資源檢索機(jī)制下的相同資源分發(fā)機(jī)制。如 Density_Replica、Random_Replica、Near_Replica。不難發(fā)現(xiàn)Random_Replica和Near_Replica中有多個(gè)下載速率陡降的點(diǎn)。相對(duì)于 Random_Replica和 Near_Replica，本文提出的 Density_Replica能提供更穩(wěn)定的資源下載服務(wù)，擁有最大的平均下載速率和最小的下載速率標(biāo)準(zhǔn)差。這是因?yàn)樵贒ensity_Replica下，由于所選擇的mesh路由器關(guān)聯(lián)了較多擁有資源的移動(dòng)客戶端節(jié)點(diǎn)，因此即使一個(gè)移動(dòng)客戶端節(jié)點(diǎn)移動(dòng)出 mesh路由器的范圍，還有多個(gè)移動(dòng)客戶端節(jié)點(diǎn)可以提供服務(wù)。而其他的2種機(jī)制中，當(dāng)移動(dòng)客戶端移動(dòng)出mesh路由器的范圍時(shí)，由于缺少更多地備份移動(dòng)節(jié)點(diǎn)，就需要重新進(jìn)行網(wǎng)絡(luò)資源檢索，以確定新的 mesh路由器來提供資源分發(fā)服務(wù)，這個(gè)過程亦會(huì)造成短暫的資源下載服務(wù)中斷。

因此，本文提出的基于密度敏感的資源檢索和分發(fā)算法Density_replica能夠取得較高的資源下載速率，并獲得最為穩(wěn)定的資源下載性能。

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

多跳無線 mesh網(wǎng)絡(luò)中移動(dòng)客戶端節(jié)點(diǎn)擁有大量的資源且具有高度動(dòng)態(tài)性，針對(duì)移動(dòng)客戶端節(jié)點(diǎn)移動(dòng)性會(huì)帶來資源下載的波動(dòng)，本文將 mesh網(wǎng)絡(luò)建模為分簇P2P結(jié)構(gòu)，提出基于分簇P2P的資源密度敏感資源檢索和分發(fā)算法。該算法將無線網(wǎng)絡(luò)中移動(dòng)客戶端的資源請(qǐng)求轉(zhuǎn)發(fā)到擁有資源最多的P2P分簇中，利用多個(gè)資源的備份，最大化降低由于節(jié)點(diǎn)移動(dòng)性而產(chǎn)生的資源下載中斷導(dǎo)致的性能下降，提高資源下載的穩(wěn)定性和下載速率。大量的仿真實(shí)驗(yàn)結(jié)果表明本文所提出的資源檢索算法具有較好的資源下載性能。

[1] AKYILDIZ I F, WANG X, WANG W. Wireless mesh networks: a survey[J]. Computer Networks, 2005, 47(4):445-487.

[2] BRUNO R, CONTI M, GREGORI E. Mesh networks:commodity multihop ad hoc networks[J]. Communications Magazine, 2005, 43(3):123-131.

[3] RIGGIO R, RASHEED T, TESTI S, et al. Interference and traffic aware channel assignment in WiFi-based wireless mesh networks[J].Ad Hoc Networks, 2011,9(5):864-875.

[4] ZHU X Q, BERND G. Distributed rate allocation for video streaming over wireless networks with heterogeneous link speeds[A]. Proceedings of the 2007 International Conference on Wireless Communications and Mobile Computing[C]. Honolulu, Hawaii, USA, 2007.296-301.

[5] TAN L S, ZHANG X M, LLH A, et al. Price-based max-min fair rate allocation in wireless multi-hop networks[J]. Communications Letters,2006,10(1):31-33.

[6] WU Y N, MUNG C, et al. Distributed utility maximization for network coding based multicasting: a critical cut approach[A].Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks,2006 4th International Symposium[C]. 2006.1-6

[7] MAGHAREI N, REJAIE R. PRIME: peer-to-peer receiver-driven mesh-based streaming[A]. 26th IEEE International Conference on Computer Communications[C]. Alaska, USA,2007.1052-1065.

[8] BEVERLY YANG B, GARCIA-MOLINA H. Designing a super-peer network[A]. Proceedings of Data Engineering[C]. Bangalore, India,2003. 49-60.

[9] ZHENG W, ZHANG S, OUYANG Y, et al. Node clustering based on link delay in P2P networks[A]. ACM Symposium on Applied Computing[C]. New Mexico, USA, 2005.744-749.

[10] SINGH A, HAAHR M. Decentralized clustering in pure P2P overlay networks using schelling's model[A]. ICC '07 IEEE International Conference[C]. Scotland, UK, 2007.1860-1866.

[11] MCDONALD A B, ZNATI T F. A mobility-based framework for adaptive clustering in wireless ad hoc networks[J]. Selected Areas in Communications, 1999,17(8):1466-1487.

[12] DAS B, BHARGHAVAN V. Routing in ad-hoc networks using minimum connected dominating sets[A]. IEEE International Conference on Communication[C]. Montreal, Canada, 1997.376-380.

[13] LAKSHMISH R, GEDIK B, LIU L. Connectivity based node clustering in decentralized peer-to-peer networks[A]. Peer-to-Peer Computing[C]. Sweden, 2003.66-73.

[14] FESSANT F L, KERMARREC A M, MASSOULIé L. Clustering in peer-to-peer file sharing workloads[A]. 3rd International Workshop on Peer-to-Peer Systems[C]. CA, USA, 2004.217-226.

[15] L?SER A, L?SER E, NAUMANN F, et al. Semantic overlay clusters within super-peer networks[A]. International Workshop on Databases,Information Systems and Peer-to-Peer Computing[C]. Berlin, Germany,2003.33-47.

[16] NG C H, SIA K C. Peer clustering and firework query model[A]. The 12th International World Wide Web Conference[C]. Montreal, Canada,2002.1-6.

[17] SINGH A, HAAHR D M. Topology adaptation in P2P networks using Schelling’s model[A]. Workshop on Emergent Behaviour and Distributed Computing[C]. Birmingham, UK, 2004. 33-38.

[18] AGRAWAL A, CASANOVA H. Clustering hosts in P2P and global computing platforms[A]. Cluster Computing and the Grid[C]. Tokyo,Japan, 2003. 367-373.

[19] BRODER A, MITZENMACHER M. Network applications of bloom filters: a survey[J]. Internet Mathematics, 2002, 1(4):485-509.

[20] NCTUns 6.0 network imulator and emulator[EB/OL]. http://nsl.csie.nctu. edu.tw/nctuns.html,2011.