面向通信扇區優化的有向傳感網絡簇路由

2021-02-25 09:11:42張馳

計算機工程與設計 2021年2期

張馳

(河南財經政法大學計算機與信息工程學院，河南鄭州 450046)

0 引言

目前，有向傳感網絡(directional sensor networks，DSNs)[1,2]在智慧城市中廣泛使用。DSN網絡是由微型的有向傳感節點(directional sensor nodes，DNs)組成。通過DNs覆蓋目標，并感知目標狀態，再將數據傳輸至基站(信宿)，進而實現對監測區域的目的。

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

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

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

然而，上述算法并沒有考慮到DNs朝向基站的扇區問題。實質上，優先選擇朝向基站的扇區內節點作為簇頭，可能會提高數據包傳輸效率。

為此，提出面向通信扇區優化的簇(communication sector optimization-based clustering，CSOC)路由。CSOC路由先從扇區角度，構建候選扇區集，再從候選扇區集中擇優選擇簇頭。簇頭間再選擇網關，進而構建頭的數據傳輸路徑。仿真結果表明，提出的CSOC路由降低了能耗，減少了數據傳輸路徑。

1 系統模型及假設

1.1 DN的感知和通信模型

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

令(xi,yi)表示DNsi的位置坐標。對于位于(x,y)位置的目標b，若滿足式(1)，則目標b在節點si覆蓋范圍內

(1)

1.2 DN節點扇區特性

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

圖2 扇區示例

2 CSOC路由

CSOC路由通過考慮節點的扇區信息、節點能量以及離基站距離，選擇最優的簇頭和網關。先尋找候選扇區，再計算候選扇區的權重值。然后, 再考慮節點的能量、距離信息選擇簇頭。再依據簇頭，選擇網關。

2.1 候選扇區

以快速傳輸數據、減少通信跳數為原則構建候選扇區。盡量選擇扇區指向基站的節點作為簇頭。因此，將指向基站的扇區納入候選扇區。引用布爾變量bi,k。若bi,k=1，表示節點si的第k個通信扇區指向基站；反之，該扇區未指向基站。

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

具體而言，對于節點si的扇區i,kF，若滿足式(2)，則將i,kF加入ψc

(2)

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

圖3 構建候選扇區的過程

2.2 節點權值

從圖3可知，位于不同扇區內的節點向基站傳輸數據的路徑并不相同。應先從扇區角度，選擇最優扇區，再選擇簇頭。為此，先計算候選扇區ψc內扇區的權重值。令Wi,k表示節點si的第k個的權重值

(3)

再針對節點扇區的權重值，并考慮節點的鄰居節點、距離以及能量信息，產生簇頭。令Qi,k表示位于以扇區k作為與基站的通信區的節點i成為簇頭的概率

(4)

(5)

(6)

(7)

2.3 簇頭選擇及簇形成

依據式(4)計算Qi,k后，再根據式(8)產生簇頭。即將具有最大Qi,c值的節點成為簇頭

(8)

若滿足式(8)，就宣告自己成為簇頭。并向鄰居節點廣播通告消息Ann_CH。Ann_CH消息內包含了簇頭的ID號以及工作的通信扇區。

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

2.4 網關的選擇

簇頭間通過網關通信。因此，每個簇頭先利用式(9)構建候選網關節點集

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

(9)

(10)

2.5 簇頭更新

在CSOC路由中，簇頭負責向基站傳輸數據。因此，相比于其它節點，簇頭的能耗速度可能更快。為此，需要對簇頭進行更新，避免簇頭能量過低，甚至消耗殆盡。

當簇頭的能量低于預定閾值Eth時，就重新啟動簇頭的選擇過程。考慮到所有節點的能量逐步減少，對閾值Eth進行動態調整，每執行一次簇頭選擇，閾值Eth就降低一部分

Eth=Eth，0<<1

(11)

3 性能分析

3.1 仿真環境

在區域1000 m×1000 m內部署200～1000個節點，目標數為50～200個目標。通過NS-2仿真軟件構建仿真平臺[11]。具體的仿真參數見表1。

表1 仿真參數

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

3.2 目標數-簇率

首先分析節點數對目標數-簇率的性能影響，其中節點數從200至900變化，每個節點的扇區數為4。目標數為120。

圖4 節點數對目標數-簇率影響

圖4顯示節點數對目標數-簇率的影響。從數據顯示，最初節點數的增加，目標數-簇率快速下降。但當節點下降至400后，目標數-簇率下降速度變緩。這符合預期，在目標數固定的情況下，節點數越多，所形成的簇越多，目標數與簇數的比值自然越小。相比于TDC，提出的CSOC路由的目標數-簇率得到提升，平均約提升至1.2。