面向通信扇區(qū)優(yōu)化的有向傳感網(wǎng)絡(luò)簇路由

張 馳

(河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 鄭州 450046)

0 引 言

目前，有向傳感網(wǎng)絡(luò)(directional sensor networks，DSNs)[1,2]在智慧城市中廣泛使用。DSN網(wǎng)絡(luò)是由微型的有向傳感節(jié)點(diǎn)(directional sensor nodes，DNs)組成。通過DNs覆蓋目標(biāo)，并感知目標(biāo)狀態(tài)，再將數(shù)據(jù)傳輸至基站(信宿)，進(jìn)而實(shí)現(xiàn)對(duì)監(jiān)測區(qū)域的目的。

與全向傳感節(jié)點(diǎn)不同，有向傳感節(jié)點(diǎn)的通信區(qū)域和感測區(qū)域具有方向性[3]。通常，DNs的通信半徑是有限的，且由電池供電。因此，DN需通過多跳才能將數(shù)據(jù)傳輸至基站。

通過分簇算法，將網(wǎng)絡(luò)劃分為層次化結(jié)構(gòu)，有利于提高數(shù)據(jù)傳輸效率和網(wǎng)絡(luò)連通率，進(jìn)而節(jié)省網(wǎng)絡(luò)能量。每個(gè)簇有一個(gè)簇頭(cluster head，CH)，簇頭收集本簇內(nèi)的節(jié)點(diǎn)(簡稱簇成員)數(shù)據(jù)[4]。簇頭通過網(wǎng)關(guān)節(jié)點(diǎn)將數(shù)據(jù)傳輸至基站(base station，BS)?，F(xiàn)存的分簇算法多數(shù)是針對(duì)全向傳感網(wǎng)絡(luò)，它們都沒有考慮到DNs的特性，如有限的工作方向、窄小的通信視角。因此，將這些分簇算法直接應(yīng)用于DSNs[5-7]，難以獲取良好的網(wǎng)絡(luò)性能。

目前，只有少數(shù)文獻(xiàn)研究了DSN網(wǎng)絡(luò)的分簇問題。文獻(xiàn)[8]提出自動(dòng)分簇算法(autonomous clustering algorithm，ACA)。但是，ACA算法最初在選擇簇頭時(shí)，并沒有考慮節(jié)點(diǎn)能量。只是在后續(xù)簇頭更新時(shí)，考慮了節(jié)點(diǎn)剩余能量。文獻(xiàn)[9]提出了基于目標(biāo)覆蓋的分布式分簇(target coverage-based distributed clustering，TDC)算法。TDC算法在選擇簇頭時(shí)，考慮了節(jié)點(diǎn)密度、剩余能量以及離基站的距離。

然而，上述算法并沒有考慮到DNs朝向基站的扇區(qū)問題。實(shí)質(zhì)上，優(yōu)先選擇朝向基站的扇區(qū)內(nèi)節(jié)點(diǎn)作為簇頭，可能會(huì)提高數(shù)據(jù)包傳輸效率。

為此，提出面向通信扇區(qū)優(yōu)化的簇(communication sector optimization-based clustering，CSOC)路由。CSOC路由先從扇區(qū)角度，構(gòu)建候選扇區(qū)集，再從候選扇區(qū)集中擇優(yōu)選擇簇頭。簇頭間再選擇網(wǎng)關(guān)，進(jìn)而構(gòu)建頭的數(shù)據(jù)傳輸路徑。仿真結(jié)果表明，提出的CSOC路由降低了能耗，減少了數(shù)據(jù)傳輸路徑。

1 系統(tǒng)模型及假設(shè)

1.1 DN的感知和通信模型

圖1 有向傳感器感知和通信模型

令(xi,yi)表示DNsi的位置坐標(biāo)。對(duì)于位于(x,y)位置的目標(biāo)b，若滿足式(1)，則目標(biāo)b在節(jié)點(diǎn)si覆蓋范圍內(nèi)

(1)

1.2 DN節(jié)點(diǎn)扇區(qū)特性

隨著電子技術(shù)的發(fā)展，DN的感知方向可以繞定點(diǎn)旋轉(zhuǎn)。即DN可以有多個(gè)扇區(qū)。當(dāng)然，在特定時(shí)刻，只有一個(gè)扇區(qū)在工作。因此，假定DN有Ωc、Ωs個(gè)通信扇區(qū)、感知扇區(qū)。用(Fk,Fk+1)表示第k個(gè)通信扇區(qū)的兩條邊線，且k∈Ωc。類似地，用(Gk,Gk+1)表示第k個(gè)感知扇區(qū)的兩條邊線，且k∈Ωs。圖2顯示了Ωc=Ωs=6的節(jié)點(diǎn)扇區(qū)示例。

圖2 扇區(qū)示例

2 CSOC路由

CSOC路由通過考慮節(jié)點(diǎn)的扇區(qū)信息、節(jié)點(diǎn)能量以及離基站距離，選擇最優(yōu)的簇頭和網(wǎng)關(guān)。先尋找候選扇區(qū)，再計(jì)算候選扇區(qū)的權(quán)重值。然后, 再考慮節(jié)點(diǎn)的能量、距離信息選擇簇頭。再依據(jù)簇頭，選擇網(wǎng)關(guān)。

2.1 候選扇區(qū)

以快速傳輸數(shù)據(jù)、減少通信跳數(shù)為原則構(gòu)建候選扇區(qū)。盡量選擇扇區(qū)指向基站的節(jié)點(diǎn)作為簇頭。因此，將指向基站的扇區(qū)納入候選扇區(qū)。引用布爾變量bi,k。若bi,k=1，表示節(jié)點(diǎn)si的第k個(gè)通信扇區(qū)指向基站；反之，該扇區(qū)未指向基站。

對(duì)于任意節(jié)點(diǎn)si，其有Ωc個(gè)通信扇區(qū)。將節(jié)點(diǎn)si與基站位置連成線sib。對(duì)于任意一個(gè)扇區(qū)k∈Ωc，若sib與扇區(qū)邊線Fk、Fk+1的兩個(gè)夾角只要有一個(gè)小于90度，該扇區(qū)i,kF就納入候選扇區(qū)集ψc。

具體而言，對(duì)于節(jié)點(diǎn)si的扇區(qū)i,kF，若滿足式(2)，則將i,kF加入ψc

(2)

如圖3所示，節(jié)點(diǎn)si的扇區(qū)i,2F的邊線F2、F3與sib的兩個(gè)夾角為∠biF2、∠biF3。依據(jù)式(2)，扇區(qū)i,1F、i,2F、i,3F和i,6F可納入候選扇區(qū)集ψc。因此，bi,1=bi,2=bi,3=bi,6=1。

圖3 構(gòu)建候選扇區(qū)的過程

2.2 節(jié)點(diǎn)權(quán)值

從圖3可知，位于不同扇區(qū)內(nèi)的節(jié)點(diǎn)向基站傳輸數(shù)據(jù)的路徑并不相同。應(yīng)先從扇區(qū)角度，選擇最優(yōu)扇區(qū)，再選擇簇頭。為此，先計(jì)算候選扇區(qū)ψc內(nèi)扇區(qū)的權(quán)重值。令Wi,k表示節(jié)點(diǎn)si的第k個(gè)的權(quán)重值

(3)

再針對(duì)節(jié)點(diǎn)扇區(qū)的權(quán)重值，并考慮節(jié)點(diǎn)的鄰居節(jié)點(diǎn)、距離以及能量信息，產(chǎn)生簇頭。令Qi,k表示位于以扇區(qū)k作為與基站的通信區(qū)的節(jié)點(diǎn)i成為簇頭的概率

(4)

(5)

(6)

(7)

2.3 簇頭選擇及簇形成

依據(jù)式(4)計(jì)算Qi,k后，再根據(jù)式(8)產(chǎn)生簇頭。即將具有最大Qi,c值的節(jié)點(diǎn)成為簇頭

(8)

若滿足式(8)，就宣告自己成為簇頭。并向鄰居節(jié)點(diǎn)廣播通告消息Ann_CH。Ann_CH消息內(nèi)包含了簇頭的ID號(hào)以及工作的通信扇區(qū)。

收到Ann_CH后(假定節(jié)點(diǎn)si為簇頭，其工作的通信扇區(qū)為k)，說明已有節(jié)點(diǎn)成為簇頭。據(jù)此，鄰居節(jié)點(diǎn)sj∈ni,k就加入該簇，以節(jié)點(diǎn)si為簇頭。

2.4 網(wǎng)關(guān)的選擇

簇頭間通過網(wǎng)關(guān)通信。因此，每個(gè)簇頭先利用式(9)構(gòu)建候選網(wǎng)關(guān)節(jié)點(diǎn)集

i←j|(sj∈Mi)&(sh∈nj,k&sh∈M)

(9)

(10)

2.5 簇頭更新

在CSOC路由中，簇頭負(fù)責(zé)向基站傳輸數(shù)據(jù)。因此，相比于其它節(jié)點(diǎn)，簇頭的能耗速度可能更快。為此，需要對(duì)簇頭進(jìn)行更新，避免簇頭能量過低，甚至消耗殆盡。

當(dāng)簇頭的能量低于預(yù)定閾值Eth時(shí)，就重新啟動(dòng)簇頭的選擇過程?？紤]到所有節(jié)點(diǎn)的能量逐步減少，對(duì)閾值Eth進(jìn)行動(dòng)態(tài)調(diào)整，每執(zhí)行一次簇頭選擇，閾值Eth就降低一部分

Eth=Eth，0<<1

(11)

3 性能分析

3.1 仿真環(huán)境

在區(qū)域1000 m×1000 m內(nèi)部署200～1000個(gè)節(jié)點(diǎn)，目標(biāo)數(shù)為50～200個(gè)目標(biāo)。通過NS-2仿真軟件構(gòu)建仿真平臺(tái)[11]。具體的仿真參數(shù)見表1。

表1 仿真參數(shù)

為了更好地分析CSOC路由性能，選擇同類路由TDC進(jìn)行比較。選擇覆蓋目標(biāo)數(shù)-簇率(coverage targets-cluster ratio，CTCR)、系統(tǒng)開銷率、網(wǎng)絡(luò)壽命以及平均路徑跳數(shù)。覆蓋目標(biāo)數(shù)-簇率等于所覆蓋的目標(biāo)數(shù)與簇的比例。該值越大，說明性能越好。

3.2 目標(biāo)數(shù)-簇率

首先分析節(jié)點(diǎn)數(shù)對(duì)目標(biāo)數(shù)-簇率的性能影響，其中節(jié)點(diǎn)數(shù)從200至900變化，每個(gè)節(jié)點(diǎn)的扇區(qū)數(shù)為4。目標(biāo)數(shù)為120。

圖4 節(jié)點(diǎn)數(shù)對(duì)目標(biāo)數(shù)-簇率影響

圖4顯示節(jié)點(diǎn)數(shù)對(duì)目標(biāo)數(shù)-簇率的影響。從數(shù)據(jù)顯示，最初節(jié)點(diǎn)數(shù)的增加，目標(biāo)數(shù)-簇率快速下降。但當(dāng)節(jié)點(diǎn)下降至400后，目標(biāo)數(shù)-簇率下降速度變緩。這符合預(yù)期，在目標(biāo)數(shù)固定的情況下，節(jié)點(diǎn)數(shù)越多，所形成的簇越多，目標(biāo)數(shù)與簇?cái)?shù)的比值自然越小。相比于TDC，提出的CSOC路由的目標(biāo)數(shù)-簇率得到提升，平均約提升至1.2。

3.3 網(wǎng)絡(luò)壽命

本小節(jié)，分析節(jié)點(diǎn)數(shù)和目標(biāo)數(shù)對(duì)網(wǎng)絡(luò)壽命的影響。采用文獻(xiàn)[12]的定義，將部署網(wǎng)絡(luò)開始時(shí)間t0至網(wǎng)絡(luò)內(nèi)出現(xiàn)第一個(gè)能量消耗殆盡的節(jié)點(diǎn)時(shí)間t1的差，即將t1-t0作為網(wǎng)絡(luò)壽命。

圖5顯示了目標(biāo)數(shù)為120、每個(gè)節(jié)點(diǎn)的扇區(qū)為4時(shí)，節(jié)點(diǎn)數(shù)對(duì)網(wǎng)絡(luò)壽命的影響。從圖5可知，節(jié)點(diǎn)數(shù)的增加，提升了網(wǎng)絡(luò)壽命。原因在于：節(jié)點(diǎn)數(shù)越多，網(wǎng)絡(luò)的總體能量越高。相比于TDC，CSOC路由的網(wǎng)絡(luò)得到提升。原因在于：CSOC路由優(yōu)化了簇頭選擇，平衡了網(wǎng)絡(luò)能耗。

圖5 節(jié)點(diǎn)數(shù)對(duì)網(wǎng)絡(luò)壽命的影響

圖6顯示了節(jié)點(diǎn)數(shù)為600、每個(gè)節(jié)點(diǎn)的扇區(qū)數(shù)為4時(shí)，目標(biāo)個(gè)數(shù)對(duì)網(wǎng)絡(luò)壽命的影響。從圖可知，在節(jié)點(diǎn)數(shù)一定情況下，目標(biāo)數(shù)的增加，降低了網(wǎng)絡(luò)壽命。這符合邏輯。目標(biāo)數(shù)的增加，就需要更多節(jié)點(diǎn)覆蓋目標(biāo)，這就加大了能量消耗。

圖6 目標(biāo)數(shù)對(duì)網(wǎng)絡(luò)壽命的影響

3.4 系統(tǒng)開銷率

先分析系統(tǒng)開銷率隨節(jié)點(diǎn)數(shù)的變化情況，如圖7所示，其中目標(biāo)數(shù)為100，每個(gè)節(jié)點(diǎn)的扇區(qū)數(shù)為4。

圖7 節(jié)點(diǎn)數(shù)對(duì)開銷率的影響

從圖7可知，節(jié)點(diǎn)數(shù)的增加提升了系統(tǒng)開銷率。原因在于：節(jié)點(diǎn)數(shù)越多，需要交互的控制包就越多，這必然增加了開銷率。與TDC算法相比，CSOC路由控制了開銷率。

圖8顯示了節(jié)點(diǎn)數(shù)為300時(shí)，目標(biāo)數(shù)為120時(shí)，節(jié)點(diǎn)扇區(qū)數(shù)對(duì)開銷率的影響。從圖8可知，扇區(qū)數(shù)的增加使開銷率呈上升趨勢。這主要是因?yàn)椋汗?jié)點(diǎn)扇區(qū)越多，選擇候選扇區(qū)以及簇頭越復(fù)雜，所產(chǎn)生的開銷就越多。與圖7類似，相比于TDC，CSOC路由仍控制了開銷。

圖8 扇區(qū)數(shù)對(duì)開銷率的影響

3.5 路徑跳數(shù)

最后，分析節(jié)點(diǎn)數(shù)對(duì)路徑跳數(shù)的影響，如圖9所示，其中目標(biāo)數(shù)為120，每個(gè)節(jié)點(diǎn)的扇區(qū)數(shù)為4。

圖9 節(jié)點(diǎn)數(shù)對(duì)路徑跳數(shù)的影響

從圖9可知，最初(節(jié)點(diǎn)數(shù)從200至400變化期間)，路徑跳數(shù)隨節(jié)點(diǎn)數(shù)的增加，快速下降。但當(dāng)節(jié)點(diǎn)數(shù)增加至400后，路徑跳數(shù)隨節(jié)點(diǎn)數(shù)增加而下降的速度變緩。原因在于：節(jié)點(diǎn)數(shù)越多，節(jié)點(diǎn)密度越高，可選的數(shù)據(jù)傳輸路徑越多，進(jìn)而產(chǎn)生最短路徑的可能性越大。相比于TDC，CSOC路由控制了路徑跳數(shù)。

4 結(jié)束語

簇結(jié)構(gòu)是提高數(shù)據(jù)傳輸效率，減少能耗的有效策略。為此，本文針對(duì)有向傳感網(wǎng)絡(luò)，面向通信扇區(qū)優(yōu)化的簇CSOC路由。CSOC路由從通信扇區(qū)角度選擇簇頭。簇頭再從兩跳鄰居節(jié)點(diǎn)擇優(yōu)節(jié)點(diǎn)網(wǎng)關(guān)。仿真結(jié)果表明，提出的CSOC路由降低了能耗，延長了網(wǎng)終壽命。