王新穎,熊 偉
(1.湖北文理學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,湖北 襄陽 441053;2.武漢大學(xué)軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室,武漢 430072)
基于簇的無線傳感器網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)機(jī)制研究
王新穎1,熊 偉2
(1.湖北文理學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,湖北 襄陽 441053;2.武漢大學(xué)軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室,武漢 430072)
如何及時(shí)有效地發(fā)現(xiàn)并使用服務(wù),是實(shí)現(xiàn)無線傳感器網(wǎng)絡(luò)實(shí)際應(yīng)用的關(guān)鍵。在分析現(xiàn)有的無線傳感器網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)機(jī)制基礎(chǔ)上,提出一種基于簇的無線傳感器網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)機(jī)制。該機(jī)制根據(jù)節(jié)點(diǎn)的綜合性能指標(biāo)值動(dòng)態(tài)選擇簇頭,并對(duì)簇頭列表中的服務(wù)請(qǐng)求和服務(wù)響應(yīng)按照優(yōu)先級(jí)級(jí)別進(jìn)行傳輸,提高了服務(wù)發(fā)現(xiàn)的性能和系統(tǒng)的穩(wěn)定性。仿真結(jié)果表明,與同類的服務(wù)發(fā)現(xiàn)機(jī)制相比,該機(jī)制在命中率、時(shí)延方面具有較大的優(yōu)越性。
無線傳感器網(wǎng)絡(luò),簇,服務(wù)發(fā)現(xiàn),命中率,時(shí)延
如何在無線傳感器網(wǎng)絡(luò)中及時(shí)有效的發(fā)現(xiàn)并使用服務(wù),是研究者近幾年來一直尋求解決的一個(gè)難題。目前已形成標(biāo)準(zhǔn)的 SLP[1],Jini[2],SSDP[3],Salutation[4]等服務(wù)發(fā)現(xiàn)機(jī)制并沒有考慮無線傳感器網(wǎng)絡(luò)自身的特性,不適合在無線傳感器網(wǎng)絡(luò)中應(yīng)用。為了解決在無線傳感器網(wǎng)絡(luò)中的服務(wù)發(fā)現(xiàn)問題,近年來,學(xué)者們紛紛在該領(lǐng)域進(jìn)行了深入的研究。文獻(xiàn)[5]提出了一種基于多播方式的無目錄結(jié)構(gòu)服務(wù)發(fā)現(xiàn)機(jī)制(HESED)。該機(jī)制的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單,健壯性高。然而,在傳感器節(jié)點(diǎn)數(shù)量巨大,服務(wù)請(qǐng)求頻繁的情況下,容易出現(xiàn)網(wǎng)絡(luò)擁堵、能量消耗過快等問題,這在無線傳感器網(wǎng)絡(luò)中是不可行的。文獻(xiàn)[6]提出了一種目錄結(jié)構(gòu)的服務(wù)發(fā)現(xiàn)機(jī)制(GSD),能夠有效提高服務(wù)發(fā)現(xiàn)的效率和系統(tǒng)的可擴(kuò)展性。但由于該服務(wù)發(fā)現(xiàn)機(jī)制采用固定的節(jié)點(diǎn)作為簇頭,導(dǎo)致簇頭能量迅速消耗殆盡而失效,影響服務(wù)發(fā)現(xiàn)的性能和系統(tǒng)的穩(wěn)定性。
針對(duì)以上存在的不足,本文提出一種基于簇的無線傳感器網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)機(jī)制(CSDM),該機(jī)制根據(jù)節(jié)點(diǎn)的綜合性能指標(biāo)值動(dòng)態(tài)選擇簇頭,并對(duì)簇頭列表中的服務(wù)請(qǐng)求和服務(wù)響應(yīng)按照優(yōu)先級(jí)級(jí)別進(jìn)行傳輸,提高了無線傳感器網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)的性能和系統(tǒng)的穩(wěn)定性。
本網(wǎng)絡(luò)模型的應(yīng)用場(chǎng)景為:節(jié)點(diǎn)隨機(jī)的分布在無線傳感器網(wǎng)絡(luò)區(qū)域內(nèi),節(jié)點(diǎn)可以在整個(gè)網(wǎng)絡(luò)區(qū)域自由移動(dòng)。
假設(shè):
①網(wǎng)絡(luò)中的所有傳感器節(jié)點(diǎn)都處于同一環(huán)境;
②每個(gè)節(jié)點(diǎn)具有唯一的ID標(biāo)示;
③無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)性能是不同的,存在一些性能優(yōu)良并且穩(wěn)定性好的節(jié)點(diǎn);
④節(jié)點(diǎn)之間的傳輸時(shí)延與節(jié)點(diǎn)間的距離成正比;
⑤每個(gè)傳感器節(jié)點(diǎn)具有一個(gè)性能指標(biāo)值p,表示節(jié)點(diǎn)的電量、計(jì)算能力、存儲(chǔ)能力以及通信能力等情況。節(jié)點(diǎn)i在時(shí)間t的性能指標(biāo)值p通過式(1)進(jìn)行計(jì)算。
其中,pi(t)表示節(jié)點(diǎn)i在時(shí)間t的性能指標(biāo)值,節(jié)點(diǎn)的剩余電量由ei(t)表示,節(jié)點(diǎn)的計(jì)算能力由ci(t)表示,節(jié)點(diǎn)的剩余存儲(chǔ)能力由si(t)表示,節(jié)點(diǎn)的通信能力由 coi(t)表示。α、β、γ、η 則分別表示 ei(t)、ci(t)、si(t)和coi(t)的權(quán)重,且α+β+γ+η=1。
1.2.1 簇的生成
在無線傳感器網(wǎng)絡(luò)的生命周期中,所有的節(jié)點(diǎn)存在3種工作狀態(tài):即FN(Free Node,自由節(jié)點(diǎn))、CH(Cluster Head,簇頭)和 CM(Cluster Member,簇成員)。初始時(shí),網(wǎng)絡(luò)內(nèi)全部的傳感器節(jié)點(diǎn)都是自由節(jié)點(diǎn),不屬于任何一個(gè)簇,處于FN狀態(tài)。初始化時(shí),無線傳感器網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)均廣播HELLO信息給它的鄰居節(jié)點(diǎn),當(dāng)某節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)的HELLO信息后,對(duì)比鄰居節(jié)點(diǎn)和自身的性能指標(biāo)值。如果一個(gè)節(jié)點(diǎn)在其所有鄰居節(jié)點(diǎn)中,具有最高的性能指標(biāo)值,將自身聲明為簇頭節(jié)點(diǎn),將狀態(tài)設(shè)為CH狀態(tài),并將該節(jié)點(diǎn)為簇頭的信息廣播通知給全部鄰居節(jié)點(diǎn)。鄰居節(jié)點(diǎn)收到消息后就近加入該簇,成為簇的成員節(jié)點(diǎn),并將其狀態(tài)設(shè)為CM狀態(tài)。
1.2.2 簇的維護(hù)
由于節(jié)點(diǎn)可以在網(wǎng)絡(luò)內(nèi)自由的移動(dòng),當(dāng)某節(jié)點(diǎn)離開它所在的簇時(shí),它告知簇頭節(jié)點(diǎn),原簇頭節(jié)點(diǎn)更新自己的簇成員列表。如果一個(gè)節(jié)點(diǎn)進(jìn)入另一個(gè)新簇范圍內(nèi),它會(huì)向新的簇頭節(jié)點(diǎn)發(fā)出加入簇的信息,從而成為新簇的一員,新簇頭節(jié)點(diǎn)也相應(yīng)更新自己的簇成員列表。對(duì)于簇頭節(jié)點(diǎn)而言,雖然它具有較高的電量,穩(wěn)定性也比較強(qiáng),一般情況下可以為簇內(nèi)節(jié)點(diǎn)提供穩(wěn)定的服務(wù)。但如果簇頭的電量降低到門限值以下,它將不再擔(dān)任簇頭,簇內(nèi)的成員節(jié)點(diǎn)會(huì)根據(jù)節(jié)點(diǎn)的性能指標(biāo)值情況重新選擇新的簇頭,原簇頭會(huì)把它保存的信息列表傳遞給新簇頭。如果由于意外原因,簇頭的電量耗盡或簇頭的離開,導(dǎo)致原簇頭不能為簇成員提供服務(wù),則原簇內(nèi)的成員節(jié)點(diǎn)也會(huì)根據(jù)性能指標(biāo)值情況重新選擇簇頭。
簇內(nèi)的成員節(jié)點(diǎn)將所能提供的服務(wù)信息(包括節(jié)點(diǎn)ID、節(jié)點(diǎn)名稱和功能描述信息)提供給自身所在簇的簇頭節(jié)點(diǎn)來實(shí)現(xiàn)服務(wù)的注冊(cè)過程。如果成員節(jié)點(diǎn)和簇頭互在雙方的通信范圍內(nèi),成員節(jié)點(diǎn)可以直接將服務(wù)信息提供給簇頭節(jié)點(diǎn),如果成員節(jié)點(diǎn)和簇頭不在雙方通信范圍內(nèi),成員節(jié)點(diǎn)需要通過中間節(jié)點(diǎn)通過多跳的方式來實(shí)現(xiàn)服務(wù)信息的發(fā)送。這樣,簇頭節(jié)點(diǎn)保存本簇成員注冊(cè)的服務(wù),并對(duì)注冊(cè)的服務(wù)列表進(jìn)行維護(hù)。如果一個(gè)成員節(jié)點(diǎn)離開一個(gè)簇加入另外一個(gè)簇,該節(jié)點(diǎn)通知原來的簇頭撤銷該節(jié)點(diǎn)注冊(cè)的服務(wù),同時(shí)向新簇的簇頭注冊(cè)服務(wù),這樣保持了服務(wù)注冊(cè)信息的一致性。
服務(wù)發(fā)現(xiàn)就是根據(jù)節(jié)點(diǎn)的服務(wù)請(qǐng)求快速、準(zhǔn)確地找到所需的服務(wù)。當(dāng)某個(gè)節(jié)點(diǎn)需要某項(xiàng)服務(wù)時(shí),首先在節(jié)點(diǎn)本身的服務(wù)描述中進(jìn)行查找,如果沒有找到所需的服務(wù),就將服務(wù)請(qǐng)求發(fā)送至節(jié)點(diǎn)所在簇的簇頭節(jié)點(diǎn),如果找到所需的服務(wù),就返回服務(wù)響應(yīng)。如果沒有找到所需的服務(wù),就將服務(wù)請(qǐng)求轉(zhuǎn)發(fā)給相鄰的簇頭進(jìn)行查找,直到找到所需的服務(wù)并返回服務(wù)響應(yīng)。找到所需的服務(wù)后,服務(wù)響應(yīng)經(jīng)由各個(gè)鄰居簇頭節(jié)點(diǎn)逐步返回,最后由請(qǐng)求服務(wù)的節(jié)點(diǎn)所在簇的簇頭返回給服務(wù)請(qǐng)求節(jié)點(diǎn)。在整個(gè)服務(wù)發(fā)現(xiàn)過程中,服務(wù)請(qǐng)求和服務(wù)響應(yīng)信息均通過簇頭進(jìn)行傳遞,因此,簇頭服務(wù)請(qǐng)求和服務(wù)響應(yīng)的傳輸機(jī)制顯得尤為重要,這在1.5節(jié)詳細(xì)論述。
1.5.1 動(dòng)態(tài)劃分簇頭的服務(wù)請(qǐng)求優(yōu)先級(jí)
簇頭節(jié)點(diǎn)在向鄰居簇頭節(jié)點(diǎn)轉(zhuǎn)發(fā)服務(wù)請(qǐng)求時(shí),由于無線傳感器網(wǎng)絡(luò)帶寬的限制,需要選擇優(yōu)先級(jí)高的服務(wù)請(qǐng)求進(jìn)行傳播。所以,有必要?jiǎng)討B(tài)地對(duì)服務(wù)請(qǐng)求信息劃分級(jí)別。通過式(2)來劃分服務(wù)請(qǐng)求的優(yōu)先級(jí)。
其中,f(t)表示服務(wù)請(qǐng)求的優(yōu)先級(jí),t表示時(shí)間長(zhǎng)短,n表示跳數(shù),λ表示時(shí)間最大值,κ表示時(shí)間門限值。從式(2)可以看出,f(t)值隨著服務(wù)請(qǐng)求時(shí)間t以及跳數(shù)n的增大而增大。
1.5.2 動(dòng)態(tài)劃分簇頭的服務(wù)響應(yīng)優(yōu)先級(jí)
節(jié)點(diǎn)請(qǐng)求的服務(wù)都要經(jīng)過簇頭轉(zhuǎn)發(fā)才能執(zhí)行,但由于無線傳感器網(wǎng)絡(luò)傳輸帶寬的限制,簇頭節(jié)點(diǎn)同時(shí)傳輸所有服務(wù)響應(yīng)是不可能的,因此,動(dòng)態(tài)地將進(jìn)入簇頭列表的服務(wù)響應(yīng)劃分等級(jí)也是必要的。對(duì)服務(wù)響應(yīng)劃分優(yōu)先級(jí),要綜合考慮該服務(wù)響應(yīng)在網(wǎng)絡(luò)中被請(qǐng)求的時(shí)間和提供該服務(wù)的節(jié)點(diǎn)個(gè)數(shù)兩個(gè)因素。通過式(3)來劃分服務(wù)響應(yīng)優(yōu)先級(jí)。
其中,f(sj)表示服務(wù)響應(yīng)sj的優(yōu)先級(jí),請(qǐng)求服務(wù)響應(yīng)sj的節(jié)點(diǎn)個(gè)數(shù)用#n(sj)表示,擁有服務(wù)響應(yīng)sj的節(jié)點(diǎn)個(gè)數(shù)用#(sj)表示。#n(sj)可以通過式(2)來計(jì)算得到。從式(3)可以看出,服務(wù)響應(yīng)的優(yōu)先級(jí)f(sj)值與#n(sj)2成正比,與#(sj)成反比。
1.5.3 傳播服務(wù)請(qǐng)求和服務(wù)響應(yīng)
通過式(2)和式(3),可以計(jì)算得到簇頭節(jié)點(diǎn)服務(wù)請(qǐng)求和服務(wù)響應(yīng)的優(yōu)先級(jí)。在t時(shí)刻,某簇頭節(jié)點(diǎn)存在10個(gè)服務(wù)請(qǐng)求和10個(gè)服務(wù)響應(yīng)需要轉(zhuǎn)發(fā),它們的優(yōu)先級(jí)各不相同。假設(shè)每個(gè)服務(wù)請(qǐng)求和服務(wù)響應(yīng)的數(shù)據(jù)量是10 kb,每個(gè)簇頭節(jié)點(diǎn)擁有120 kb的帶寬可以傳輸數(shù)據(jù)信息,按照服務(wù)請(qǐng)求和服務(wù)響應(yīng)1:1的帶寬比例計(jì)算,每個(gè)簇頭節(jié)點(diǎn)最多只能同時(shí)傳輸6個(gè)服務(wù)請(qǐng)求和6個(gè)服務(wù)響應(yīng)。也就是說,由于無線傳感器網(wǎng)絡(luò)傳輸帶寬的限制,簇頭節(jié)點(diǎn)沒有能力同時(shí)傳輸表1中所有的服務(wù)請(qǐng)求和服務(wù)響應(yīng)。因此,本文依據(jù)優(yōu)先級(jí)排序策略[7],把優(yōu)先級(jí)高的服務(wù)請(qǐng)求和服務(wù)響應(yīng)傳送給它的鄰居簇頭節(jié)點(diǎn)。
為了驗(yàn)證CSDM的性能,本文采用OMNet++[8]進(jìn)行仿真分析,分別與文獻(xiàn)[5]提出的無目錄結(jié)構(gòu)的服務(wù)發(fā)現(xiàn)機(jī)制(HESED)和文獻(xiàn)[6]提出的目錄結(jié)構(gòu)的服務(wù)發(fā)現(xiàn)機(jī)制(GSD)進(jìn)行性能比較。
在仿真實(shí)驗(yàn)中,將網(wǎng)絡(luò)規(guī)模設(shè)置為200個(gè)節(jié)點(diǎn),網(wǎng)絡(luò)拓?fù)浞秶O(shè)置為800m×800m。隨機(jī)選擇節(jié)點(diǎn)作為服務(wù)請(qǐng)求者或服務(wù)提供者,每個(gè)節(jié)點(diǎn)可以請(qǐng)求多個(gè)服務(wù),多個(gè)節(jié)點(diǎn)也可以請(qǐng)求同一個(gè)服務(wù)。假設(shè)每個(gè)節(jié)點(diǎn)僅提供一種服務(wù),令α=0.4,β=0.1,γ=0.3,η=0.2。仿真了 2種情形。
①將節(jié)點(diǎn)的傳輸半徑設(shè)置為80m,節(jié)點(diǎn)的運(yùn)動(dòng)速度在2m/s~12m/s范圍內(nèi)變化,分別仿真了命中率、時(shí)延與節(jié)點(diǎn)速度的關(guān)系。
圖1是命中率與節(jié)點(diǎn)速度關(guān)系的仿真結(jié)果。由圖1可知,HESED的命中率最低,在70%以下,因?yàn)镠ESED的服務(wù)請(qǐng)求采用多播方式。GSD采用了目錄結(jié)構(gòu)的服務(wù)發(fā)現(xiàn)機(jī)制,命中率在70%以上。CSDM在GSD的基礎(chǔ)上,動(dòng)態(tài)選擇簇頭,受節(jié)點(diǎn)速度的影響較小,在一定程度上提高了服務(wù)發(fā)現(xiàn)的命中率,命中率在77%以上。
圖2是時(shí)延與節(jié)點(diǎn)速度關(guān)系的仿真結(jié)果。由圖2可知,HESED的時(shí)延最大,這是因?yàn)镠ESED的多播機(jī)制容易導(dǎo)致網(wǎng)絡(luò)信道沖突。在CSDM服務(wù)發(fā)現(xiàn)機(jī)制中,由于簇頭將列表中的服務(wù)請(qǐng)求和服務(wù)響應(yīng)按照優(yōu)先級(jí)級(jí)別進(jìn)行傳輸,提高了服務(wù)發(fā)現(xiàn)效率,因而時(shí)延最小。在節(jié)點(diǎn)速度為8m/s時(shí),CSDM的時(shí)延比GSD降低了42.1%,比HESED降低了66.7%。
圖1 命中率與節(jié)點(diǎn)速度的關(guān)系
圖2 時(shí)延與節(jié)點(diǎn)速度的關(guān)系
②將節(jié)點(diǎn)的運(yùn)動(dòng)速度設(shè)置為8m/s,節(jié)點(diǎn)傳輸半徑在20m~120m范圍內(nèi)變化,分別仿真了命中率、時(shí)延與節(jié)點(diǎn)傳輸半徑的關(guān)系。
圖3是命中率與節(jié)點(diǎn)傳輸半徑關(guān)系的仿真結(jié)果。由圖3可知,隨著節(jié)點(diǎn)傳輸半徑的增加,GSD和CSDM的命中率均呈現(xiàn)上升趨勢(shì),這是由于節(jié)點(diǎn)傳輸半徑增加之后,服務(wù)請(qǐng)求的傳播速度加快。當(dāng)節(jié)點(diǎn)傳輸半徑小于100m時(shí),HESED的命中率隨節(jié)點(diǎn)傳輸半徑的增加呈現(xiàn)下降趨勢(shì),但當(dāng)節(jié)點(diǎn)傳輸半徑大于100m后,隨著節(jié)點(diǎn)傳輸半徑的增加,HESED的命中率卻呈現(xiàn)下降趨勢(shì),這是由于多播方式導(dǎo)致信道沖突的原因。
圖3 命中率與節(jié)點(diǎn)傳輸半徑的關(guān)系
圖4 時(shí)延與節(jié)點(diǎn)傳輸半徑的關(guān)系
圖4是時(shí)延與節(jié)點(diǎn)傳輸半徑關(guān)系的仿真結(jié)果。由圖4可知,在節(jié)點(diǎn)傳輸半徑相同的情況下,CSDM時(shí)延最小,比如,在節(jié)點(diǎn)的傳輸半徑值為80m時(shí),CSDM的時(shí)延比GSD降低了57.6%,比HESED降低了88.3%。
本文提出一種基于簇的無線傳感器網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)機(jī)制。與文獻(xiàn)[5]提出的HESED服務(wù)發(fā)現(xiàn)機(jī)制及文獻(xiàn)[6]提出的GSD服務(wù)發(fā)現(xiàn)機(jī)制相比,該機(jī)制能有效提高命中率,縮短時(shí)延,適用于大規(guī)模的無線傳感器網(wǎng)絡(luò)。
[1]PatelBI.ASurvey of Service Discovery Architecture of MANET with AODV-SD[J]. International Journal of Computer Applications Technology and Research,2013,2(1): 59-62
[2] Yu C,Yao D,Li X,et al.Location-aware Private Service Discovery in Pervasive Computing Environment[J].Information Sciences,2013,230(1):78-93.
[3]Dittrich A,Lichtblau B,Rezende R,etal.Modeling ResponsivenessofDecentralized Service Discovery inWirelessMesh Networks[M].Measurement,Modelling,and Evaluation of Computing Systems and Dependability and Fault Tolerance.Springer InternationalPublishing,2014:88-102.
[4] Thompson M S,Midkiff SF.Service Description and Dissemination for Service Discovery in Pervasive Computing Environments[J].International Journal of Ad Hoc and U-biquitousComputing,2013,12(4):193-204.
[5]Hassanein H,Yang Y,MawjiA.A New Approach to Service Discovery inWirelessMobile Ad Hoc Networks[J].International JournalofSensorNetworks,2010,2(1):135-145.
[6]李巧勤,吳磊.一種基于團(tuán)體的無線傳感器網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn) 協(xié) 議 [J].小 型 微 型 計(jì) 算 機(jī) 系 統(tǒng) ,2012,33(6):1262-1267.
[7] Wolfson O,Xu B,Yin H B,et al.Search-and-Discover in Mobile P2PNetwork Databases[C]//Proceedings of the 26th IEEE International Conference on Distributed Computing Systems,2009.
[8]趙永利,張杰.OMNet++與網(wǎng)絡(luò)仿真[M].北京:人民郵電出版社,2012.
Research of Service Discovery M echanism Based on Cluster forW irelessSensor Networks
WANGXin-ying1,XIONGWei2
(1.School of Mathematics and Computer Science,HubeiUniversity of Arts and Science,Xiangyang 441053,China;2.State Key Laboratory of Software Engineering,Wuhan University,Wuhan 430072,China)
The key of applying wireless sensor networks in reality lies on how to find and use the service in time and with efficiency.Following the analysis of existing service discovery mechanism for wireless sensor networks,this paper proposes a service discovery mechanism based on cluster for wireless sensor networks.The mechanism dynamically selects cluster head nodes according to the comprehensive performance index.Service requests and service response in the list of cluster head are transmitted according to the priority levels.It can improve the performance of service discovery and the stability of system.The performance of simulations shows that it is better than those similar service discoverymechanisms proposed in hit ratio and delay.
wirelesssensornetworks,cluster,service discovery,hit ratio,delay
TP393
A
1002-0640(2015)11-0036-03
2014-09-28
2014-11-17
王新穎(1976- ),男,河南平頂山人,碩士,講師。研究方向:無線網(wǎng)絡(luò)、W eb服務(wù)發(fā)現(xiàn)。