董忠磊，范通讓

（石家莊鐵道大學(xué) 信息科學(xué)與技術(shù)學(xué)院，河北 石家莊 050043）

移動(dòng)自組網(wǎng)是一種無(wú)基礎(chǔ)設(shè)施的多跳無(wú)線網(wǎng)絡(luò)，在移動(dòng)自組網(wǎng)中每個(gè)節(jié)點(diǎn)同時(shí)充當(dāng)著節(jié)點(diǎn)和路由的作用［1］，由于其組網(wǎng)靈活被廣泛應(yīng)用到抗震救災(zāi)、現(xiàn)場(chǎng)指揮、臨時(shí)會(huì)議、資源共享等場(chǎng)合。移動(dòng)自組網(wǎng)沒(méi)有特定的網(wǎng)絡(luò)中心，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)同時(shí)扮演著客戶端和服務(wù)器的雙重角色［2］，網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)體差異，使得不同的節(jié)點(diǎn)擁有的資源不盡相同，節(jié)點(diǎn)極為渴求自己所不具備的必要資源，但是卻不能有一個(gè)“高層節(jié)點(diǎn)”統(tǒng)一滿足，移動(dòng)自組網(wǎng)中的服務(wù)發(fā)現(xiàn)協(xié)議應(yīng)運(yùn)而生。

隨著多媒體應(yīng)用日益普及，在移動(dòng)自組網(wǎng)資源發(fā)現(xiàn)過(guò)程提供Qos已經(jīng)逐漸成為移動(dòng)自組網(wǎng)研究的一個(gè)重要領(lǐng)域，筆者研究提出了將Qos約束條件應(yīng)用到移動(dòng)自組網(wǎng)隨機(jī)游走資源發(fā)現(xiàn)協(xié)議中，以此來(lái)提高移動(dòng)自組網(wǎng)服務(wù)發(fā)現(xiàn)的質(zhì)量。

1 相關(guān)工作

目前移動(dòng)自組網(wǎng)中的關(guān)于資源發(fā)現(xiàn)問(wèn)題得到了廣泛的研究，已經(jīng)提出了許多資源發(fā)現(xiàn)協(xié)議。文獻(xiàn)［3］提供了一種針對(duì)節(jié)點(diǎn)運(yùn)動(dòng)速度較快的情況下的資源發(fā)現(xiàn)協(xié)議—泛洪查詢。當(dāng)某個(gè)主機(jī)需要某種資源的時(shí)候只需要發(fā)送一個(gè)針對(duì)該資源的查詢廣播就可以了。但是當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量很大時(shí)，使用這種方式需要轉(zhuǎn)發(fā)大量的資源發(fā)現(xiàn)包，嚴(yán)重增加了網(wǎng)絡(luò)的負(fù)擔(dān)。文獻(xiàn)［4］提出了一種基于地理信息的資源定位協(xié)議（GCLP），這種方法因?yàn)樾枰@取地理位置信息并且周期性地廣播地理信息所以同樣耗費(fèi)能量和帶寬資源。文獻(xiàn)［5］提出了應(yīng)用于MANET的上下文相關(guān)的服務(wù)發(fā)現(xiàn)協(xié)議（CBSDP）。移動(dòng)節(jié)點(diǎn)根據(jù)所處地理位置布置的傳感器節(jié)點(diǎn)提供的環(huán)境信息，執(zhí)行應(yīng)用程序所規(guī)定的操作。文獻(xiàn)［6］在理論上分析了分布式系統(tǒng)中使用Epidemic模型（模擬傳染病的擴(kuò)散過(guò)程）進(jìn)行信息擴(kuò)散的性能，給出了需要解決的問(wèn)題以及影響性能的一些參數(shù)。文獻(xiàn)［7］提出了一種基于場(chǎng)論的資源發(fā)現(xiàn)協(xié)議。每個(gè)節(jié)點(diǎn)都具有類似于電場(chǎng)中的電壓，查詢轉(zhuǎn)發(fā)路徑是隨著資源“電壓”高的節(jié)點(diǎn)進(jìn)行。文獻(xiàn)［9］提出了一種基于隨機(jī)游走的資源發(fā)現(xiàn)協(xié)議。網(wǎng)絡(luò)中的節(jié)點(diǎn)在查詢轉(zhuǎn)發(fā)時(shí)候使用隨機(jī)游走方法，這種方法大大減少了網(wǎng)絡(luò)中查詢包的數(shù)量，降低了網(wǎng)絡(luò)開(kāi)銷。但是以上幾個(gè)提出的資源發(fā)現(xiàn)協(xié)議都沒(méi)有考慮Qos，本文就是在文獻(xiàn)［10］提出的隨機(jī)游走資源發(fā)現(xiàn)協(xié)議的基礎(chǔ)上加上Qos約束條件，來(lái)滿足特殊應(yīng)用對(duì)于Qos的需求。

2 Qos約束隨機(jī)游走在移動(dòng)自組網(wǎng)資源發(fā)現(xiàn)中的應(yīng)用

2.1 移動(dòng)自組網(wǎng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

考慮的移動(dòng)自組網(wǎng)是由Laptop、PDA、智能手機(jī)等組成的網(wǎng)絡(luò)，它們之間通過(guò)無(wú)線wifi、藍(lán)牙或紅外線等技術(shù)進(jìn)行互連，具體的拓?fù)浣Y(jié)構(gòu)如圖1所示。

2.2 Qos約束指標(biāo)計(jì)算表達(dá)式

考慮的Qos約束指標(biāo)主要包含節(jié)點(diǎn)剩余帶寬（bandwidth）、延遲（link delay）、丟包率（packet loss rate），下面分別給出其計(jì)算表達(dá)式［8］。表1給出表達(dá)式當(dāng)中所用到的符號(hào)、縮略詞及其含義。

圖1 移動(dòng)自組網(wǎng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

表1 符號(hào)及其含義

（1）剩余帶寬

節(jié)點(diǎn)的剩余帶寬通過(guò)考慮節(jié)點(diǎn)無(wú)線信道狀態(tài)即共享無(wú)線媒體的空閑時(shí)間來(lái)進(jìn)行估算。每個(gè)節(jié)點(diǎn)在觀察時(shí)間間隔TB內(nèi)監(jiān)聽(tīng)信道的狀態(tài)來(lái)確定空閑時(shí)間?？臻e時(shí)間Ii通過(guò)增加信道前一個(gè)忙碌時(shí)間結(jié)束到下一個(gè)忙碌時(shí)間開(kāi)始的數(shù)目來(lái)計(jì)算?？偟目臻e時(shí)間包括幾個(gè)空閑插槽n?？偟目臻e時(shí)間是所有n的總和?？偟男诺缼払Wtotal的計(jì)算公式如公式（1）所示。

（2）連接延遲

每個(gè)節(jié)點(diǎn)的連接延遲DL由輸入隊(duì)列延遲、處理延遲、傳播延遲和重傳延遲。Pi，a為包i到達(dá)節(jié)點(diǎn)的時(shí)間，Pi，c為確認(rèn)數(shù)據(jù)包的時(shí)間。包的連接延遲為到達(dá)時(shí)間和確認(rèn)時(shí)間的差值。在一定時(shí)間內(nèi)m個(gè)數(shù)據(jù)包的平均延遲TD表達(dá)式為：

（3）丟包率

丟包是由于緩沖區(qū)溢出和重傳引起的。丟包率PR為所有丟失包的總和，No為溢出所導(dǎo)致的丟包，Nr為重傳包的數(shù)量，那么在一段時(shí)間TP內(nèi)總的丟包率為：

通過(guò)以上得到的公式（1）、公式（2）和公式（3），在加入w1、w2、w3參數(shù)之后得到各個(gè)節(jié)點(diǎn)Qos計(jì)算表達(dá)式：

其中w1、w2、w3為根據(jù)用戶對(duì)Qos需求各個(gè)指標(biāo)所對(duì)應(yīng)的權(quán)重，用戶不同的Qos需求所對(duì)應(yīng)w1、w2、w3的值也會(huì)不同，例如當(dāng)用戶對(duì)某項(xiàng)服務(wù)需求中的帶寬占主要作用時(shí)w1的權(quán)重就會(huì)高于其它指標(biāo)。

3.3 Qos約束隨機(jī)游走資源發(fā)現(xiàn)協(xié)議

隨機(jī)游走資源發(fā)現(xiàn)協(xié)議就是移動(dòng)自組網(wǎng)節(jié)點(diǎn)在進(jìn)行資源服務(wù)請(qǐng)求分發(fā)過(guò)程中采用隨機(jī)游走方式，節(jié)點(diǎn)在接收到資源服務(wù)請(qǐng)求包后查看自身是否能夠提供相應(yīng)可利用資源，如果可以那么就給資源請(qǐng)求者發(fā)送回復(fù)包，反之把資源服務(wù)請(qǐng)求轉(zhuǎn)發(fā)給隨機(jī)挑選的鄰居節(jié)點(diǎn)，這樣一直循環(huán)執(zhí)行下去直到找到滿足服務(wù)要求的節(jié)點(diǎn)為止。

Qos約束隨機(jī)游走資源發(fā)現(xiàn)協(xié)議將用戶對(duì)節(jié)點(diǎn)在資源搜索過(guò)程中的Qos需求應(yīng)用到隨機(jī)游走協(xié)議中，使節(jié)點(diǎn)在轉(zhuǎn)發(fā)資源服務(wù)請(qǐng)求時(shí)不只是隨機(jī)的選取鄰居節(jié)點(diǎn)作為下一跳，而且還要使用Qos來(lái)評(píng)估隨機(jī)選取的節(jié)點(diǎn)是否能夠達(dá)到要求，如果不能達(dá)到要求那么就舍棄，最終得到一條滿足用戶Qos需求的資源發(fā)現(xiàn)最優(yōu)路徑，具體步驟如下：

（1）移動(dòng)自組網(wǎng)節(jié)點(diǎn)運(yùn)行Qos約束隨機(jī)游走資源發(fā)現(xiàn)協(xié)議，設(shè)定Qos閥值TS。

（2）資源請(qǐng)求節(jié)點(diǎn)發(fā)出資源服務(wù)請(qǐng)求包，節(jié)點(diǎn)利用隨機(jī)游走協(xié)議隨機(jī)的從其鄰居節(jié)點(diǎn)中選取下一跳節(jié)點(diǎn)。

（3）資源請(qǐng)求節(jié)點(diǎn)搜集2步驟中挑選的下一跳節(jié)點(diǎn)信息（剩余帶寬、連接延遲、丟包率、剩余電量）。

（4）資源請(qǐng)求節(jié)點(diǎn)利用第3步驟中搜集到的信息利用公式（5）進(jìn)行計(jì)算求得下一跳節(jié)Qvalue點(diǎn)值，將Qvalue與Qos閥值TS進(jìn)行比較如果大于或者等于那么保留節(jié)點(diǎn)，反之丟棄該下一跳節(jié)點(diǎn)。

（5）判斷是否找到服務(wù)資源提供節(jié)點(diǎn)，如果找到則停止搜索過(guò)程，服務(wù)提供節(jié)點(diǎn)發(fā)送回復(fù)包，否則跳到步驟2，直到找到服務(wù)資源提供節(jié)點(diǎn)為止。

流程圖如圖2所示。

筆者提出的移動(dòng)自組網(wǎng)Qos約束隨機(jī)游走資源發(fā)現(xiàn)協(xié)議目前只是處于理論研究階段，接下來(lái)將使用NS2網(wǎng)絡(luò)仿真工具通過(guò)與未加Qos約束的隨機(jī)游走資源發(fā)現(xiàn)協(xié)議進(jìn)行仿真比較來(lái)驗(yàn)證改進(jìn)協(xié)議的性能。

圖2 Qos約束隨機(jī)行走資源發(fā)現(xiàn)協(xié)議運(yùn)行流程

4 結(jié)語(yǔ)

提出的Qos約束隨機(jī)游走資源發(fā)現(xiàn)協(xié)議在原有隨機(jī)游走資源發(fā)現(xiàn)協(xié)議的基礎(chǔ)上加入Qos約束條件，使得節(jié)點(diǎn)在資源請(qǐng)求轉(zhuǎn)發(fā)過(guò)程中更好的滿足用戶對(duì)Qos的需求，最終尋找一條滿足資源請(qǐng)求者Qos需求的源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最優(yōu)路徑。因此，對(duì)移動(dòng)自組網(wǎng)相關(guān)領(lǐng)域還需要進(jìn)行深入的研究，比如（1）考慮更多的Qos約束條件（節(jié)點(diǎn)剩余電量），（2）對(duì)Qos約束隨機(jī)游走資源發(fā)現(xiàn)協(xié)議進(jìn)行仿真實(shí)驗(yàn)，（3）通過(guò)實(shí)驗(yàn)來(lái)總結(jié)如何根據(jù)用戶Qos需求合理的分配Qos約束條件的權(quán)重等等。

［1］Mahmoud Al－shugran，Osman Ghazali，Suhaidi Hassan，Kashif Nisarn，A.Suki M.Arif.A qualitative comparison evaluation of the greedy forwarding strategies in Mobile Ad Hoc Network［M］.Journal of Network and Computer Applications，2013（36）.887－897.

［2］R Iannella.Internet Resource Discovery Issues［EB/OL］.Available at archive.http：dstc.edu.au RDU reports Quest－Net95.html.

［3］Jivodar B.Tchakarov，Nitin H Vaidya.Efficient Content Location inWireless Ad Hoc Networks［C］.IEEE International Conference on Mobile DataManagement（MDM’04），IEEE Computer Society，Berkeley，California January，2004：74－87.

［4］Mohamed Khedr，Ahmed Kannouch.ACAN－AD HOC CONTEXT AWARE NETWORK［C］.Proceedings of the 2002 IEEE Canadian Conference on Electrical＆Computer Engineering.IEEE Computer Society，Manitoba，Canada，200：1342－1346.

［5］Patrick T Eugster，Rachid Guerraoui，Anne－Marie Kermarrec，etal.Epidemic Information Dissemination in Distributed Systems［J］.Computer，IEEE Computer Society，2004，37（5）：60－67.

［6］Vincent Lenders，Martin May，Bernhard Plattner.Service Discovery in Mobile Ad Hoc Networks：AField Theoretic Approach［C］.Proceedings of the Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks（WoWMoM＇05）.IEEE Computer Society，Italy，2005：120－130.

［7］Hamideh Babaei，Mahmood Fathy，Morteza Romoozi.Modeling and optimizing Random Walk content discovery protocol over mobile ad－h(huán)oc networks［M］.Performance Evaluation，2014.18－29.

［8］V.R.Budyal，S.S.Manvi.ANFIS and agent based bandwidth and delay aware anycast routing in mobile ad hoc networks［M］.Journal of Network and Computer Applications，2014.140－151.