基于事件的移動認知無線傳感器網分簇算法①

譚 龍,王 方

(黑龍江大學 計算機科學與技術學院,哈爾濱 150080)

無線傳感器網絡(Wireless Sensor Network,WSN)由大量的傳感器節點組成,這些節點密集地部署在一個特定的區域用于收集關于目標或事件產生的數據,并提供各種傳感和監測應用程序,作為一種很有前途的數據采集技術,在物聯網中得到了廣泛的應用,成為重要的基礎網絡之一[1,2].由于無線業務的爆炸式增長使得未授權的頻譜日益擁擠,導致運行在未授權頻譜上的無線傳感器網絡受到了嚴重干擾.認知無線電(Cognitive Radio,CR)技術已經發展成為解決頻譜短缺問題的一種有效方法,它允許對許可頻譜進行機會性訪問并廣泛應用于環境,軍事,運輸等多個領域[3].無線傳感器網絡受益于CR 技術的這一優勢克服了頻譜匱乏的挑戰.為此,通過在無線傳感器網絡中加入動態頻譜接入(Dynamic Spectrum Access,DSA)方案,提出了一種新的無線網絡模式——認知無線傳感器網絡(Cognitive Radio Sensor Networks,CRSNs)[4].

CRSN 同無線傳感器網絡中的固定頻譜分配方法不同,節點通過機會主義利用空閑頻譜.頻譜的機會使用由認知循環操作完成,包括頻譜感知、頻譜決策、頻譜共享和頻譜遷移.CRSN 節點通過頻譜感知來確定空閑頻譜,通過頻譜決策來選擇它們要使用的頻譜,根據主用戶(Primary User,PU)的活動進行頻譜切換來改變信道[4].盡管CR 技術使用不同頻段讓無線通信更靈活,但它們也帶來了一些問題.第一,動態無線電環境中的路由受限于頻譜可用性；第二,認知循環操作會中斷傳感器節點之間的傳輸；第三,主用戶的活動會影響數據傳輸的成功率.如果節點是移動的,這些問題會更復雜.節點的移動性導致頻繁的拓撲變化.此外,事件驅動的通信特性會導致突發的流量,造成信道沖突和數據包丟失.

本文提出了基于事件的移動認知無線傳感器網的分簇算法(Event based clustering algorithm for Mobile Cognitive radio sensor networks,EMC).該算法在事件發生后根據移動節點當前位置和在區域內停留時間來確立合格節點,而后計算簇頭權值來選擇簇頭.設計了直接分簇模式,并進行簇頭與成員節點間的連接時間預估計,簇頭再根據簇中每個成員移動節點的預估計連接時間以TDMA 方式進行通信,分配給成員節點時隙和空閑信道用來數據傳輸.這樣確保了簇的穩定性,從而提高了數據傳輸率,并減少了由于簇成員移動變化而帶來的控制開銷和能量消耗.

1 相關工作

在現有的移動節點分簇算法中,WSN 中分簇算法是比較多比較成熟,WSN 的分簇算法在提高網絡性能,延長網絡生命周期等方面取得了一些成功.WSN 設計分簇方案目的是以最小能耗收集信息[5].低能量自適應分簇層次移動(LEACH-mobile)算法[6],通過在LEACH協議中加入節點成員聲明來支持節點的移動性.傳感器在連續兩幀期間未接收來自其簇頭的請求,就認為自己已離開簇,因此它將廣播一個簇加入請求消息,以便加入新簇并避免丟失更多的數據包.因此,LEACHmobile 算法以增加控制開銷為代價,提高了包傳輸的成功率.文獻[7]中提出了一種基于移動性度量的LEACH移動增強協議,該協議用于簇頭選舉,選擇一個具有較小移動性的節點成為簇頭.文獻[8]提出兩種基于三層結構的移動WSN 分簇算法,最大限度地減少數據損失和提高能量效率.然而,所有這些分簇方案都假設固定信道分配,它們無法處理頻譜感知和信道切換等問題.因此,這些方案不適合CRSNs.

文獻[9]提出了一種基于事件的移動認知無線傳感網絡分簇算法,算法分為兩個階段,首先尋找適合成簇的節點,其次這些節點利用空閑頻譜分簇,率先把節點移動性應用到CRSN 當中.文獻[10]研究了多信道CRSNs 的動態頻譜訪問的問題.文中采用了數據包大小可變的自適應技術,來適應可變信道上的傳輸,更充分利用了傳感器的能量.文獻[11]提出了一種新的節點選擇方案,以提高CRSNs 的協作頻譜感知能量效率.除此之外,文中所提出的方案可在一定程度上有效平衡不同傳感器之間的能量消耗.文獻[12]中提出了一種基于能量感知分簇的CRSN 路由算法(EACRP),該算法同時考慮了能量和動態頻譜問題.EACRP 采用自組織分布式成簇,通過產生最佳簇數來獲得較少的平均節點功率.為了減輕PUs 的影響,EACRP 形成具有更多共用信道的簇,并在選擇用于簇內通信的數據信道時采用協作感測的概念.文獻[13]提出了一種用于CRSN 的低能量自適應不均勻分簇層次結構,采用不均勻分簇方法來平衡多跳傳輸方式下簇頭之間的能耗.仿真結果表明,該算法不僅可以有效地平衡簇頭中的能量消耗和CRSN中的網絡負載,還可以顯著延長網絡生命周期.

2 系統模型

2.1 網絡模型

傳感器網絡由分布在監測區域內的n個移動傳感器節點組成,具體信息：

1)用戶：PUs 無限制使用授權信道,次用戶(Secondary User,SU)在沒有PUs 活動的情況下,可以機會主義訪問授權信道；

2)節點：傳感器節點具有相同的初始能量、傳輸范圍,并且可以實現空閑頻譜的感知.

3)信道：網絡中存在M個具有唯一ID 的非重疊正交信道；兩個相鄰的CRSN 節點如果有共同的信道,則它們是互相連接的；存在一個公共控制信道(Common Control Channel,CCC)用來交換控制信息,并且每個節點通過鄰居發現都獲得一跳鄰居節點及其空閑信道.

4)定位：每個傳感器由定位算法計算出自己的二維坐標以及自身速度.

5)移動：傳感器節點根據隨機航點移動模型而移動[14].

6)時鐘：假設節點均時鐘同步,且事件結束前非簇頭合格節點在其分配的時隙中總有數據要發送到簇頭.

通信由事件驅動,位于事件區域內的CRSN 節點檢測事件,這些節點生成傳遞到sink 的數據包.CRSN事件覆蓋范圍用虛線表示,如果PUs 活躍,則SUs 應該機會主義訪問信道,具體過程如圖1所示.

圖1 航點模型

2.2 隨機航點模型

移動節點隨機選擇一個目標位置,然后從該位置向目標位置移動,速度介于[vmin,vmax]之 間,其中vmin是節點的最小速度,vmax是節點的最大速度.如果節點移動到邊界,它將以相同的速度以邊界為邊進行反射,入射角等于反射角.如果節點移動到目標位置后,將重新選擇新的目標位置進行移動,如圖2所示.

圖2 網絡模型

2.3 能耗模型

移動CRSN 節點的能耗主要包括頻譜感知、頻譜切換、數據傳輸、數據接收和節點移動的能耗.本文使用eswitch分別表示信道切換的能量消耗,由于信道感知是每個移動節點常見的周期性過程,所以其能量消耗不予考慮.在模擬中不考慮遮蔽損耗的影響,同時假設無線電信道是對稱的,本文采用文獻[12]給出的無線電能量耗散模型.在該模型中,發射器和接收器之間距離為d的情況下發送和接收k位消息的能耗表示為：

其中,Etran為傳輸能耗,Erec為接收能耗,eampdε為傳輸放大器的能耗,其中 ε為傳播指數,根據發射器和接收器的傳輸條件Edis的取值范圍在2 到4.Edis為運行發射器或接收器中電路的能耗.本文中通訊能量參數設置為：Edis=50nJ/bit,eamp=10pJ/bit/m2,ε=2.5和eswitch=40mJ.

3 分簇算法

3.1 合格節點的選擇

事件區域內的移動節點檢測到事件后,自身狀態由Snone變為Seligible,表示該節點為合格節點,并向周圍一跳鄰居節點發送請求消息,鄰居節點收到請求消息將返回自己的坐標,事件內的節點選擇一個橫坐標距離自己最遠的非事件區域節點,經事件區域內節點協調,確定一個區間作為合格節點區域.事件區域節點通過公共控制信道將合格節點信息(Eligible Node Information,ENI)發送給它們的單跳鄰居節點,ENI 中包含控制字段、節點id、節點位置信息和區域信息.

假設任意節點需要n個時間片來傳送數據,且一個時間片長為 τ,那么節點在合格區域內的時間應大于nτ才能保證數據的順利傳輸.接收到ENI 的節點發現自己位于該區域內,且其縱坐標比發送者的縱坐標距離sink 更近,并計算自身在區域內停留時間,如果停留時間大于nτ,節點狀態變為Seligible.新的合格節點將ENI 發送到自己的一跳鄰居,同時區域內的節點如果有一跳鄰居位于區域外且正向區域內移動,則該節點狀態設置為Sstandby,該過程持續到ENI 到達sink.不符合條件的移動節點不發送ENI 消息,為了不朝sink 以外的方向進一步擴大區域.

移動節點1,2,3 是位于事件區域的節點,通過不在事件區域內節點4 和5 反饋的數據,節點1 發現節點4 的水平位置距離自己最遠,同理節點2 發現節點6 的水平位置距離自己最遠,由事件區域內節點協調,劃分出一個區域,該區域是節點4 與節點6 橫坐標區間,如圖3所示.

圖3 合格節點選擇模型圖

合格節點確定的EMC 算法以分布式的方式確定合格節點,在此階段,本文假設傳感器節點密度足夠大.EMC 算法的步驟如流程圖4所示.

圖4 合格節點選擇流程圖

算法1.合格節點選擇1：Consider node where is a set of nodes in the network i V 2：if Node detects event then 3：It is eligible for clustering i 4：State()=“Eligible”i 5：sending inquiry request to one-hop neighbors other than event detecting neighbors(x0,x1)6：calculate and select an interval 7：Start sending ENI to one-hop neighbors other than event Detecting neighbors 8：else 9：if It receives ENI from its neighbor then(x0,x1)10：judge whether it is in the internal or not xi∈(x0,x1)11：if then 12：calculate i residence time t in (x0,x1)

13：compare the distance yi,sink≤yENI?sender,sink∧yi,event≥yENI?sender,event∧t＞nτ 14：if 15：then Node i is eligible for clustering 16：State(i)=“Eligible”17：Send ENI to one-hop neighbors 18：end if xi?(x0,x1)∧i(x0,x1)∧i ＞nτ 19：if direction to residence time then i 20：Node is a candidate for clustering i 21：State()=“Standby”22：else 23：Not eligible 24：end if 25：else 26：Not eligible 27：end if 28：else i 29：Node is not eligible 30：end if 31：end if

3.2 簇頭選擇

本文使用啟發式算法進行簇頭選擇.簇頭選擇時充分考慮了頻譜可用性、能量損耗、節點移動性等多項因素進行權值處理,最大權值節點作為簇頭,選擇的參數如下：

1)節點速度(vi?current)：選擇速度較低的節點作為簇的簇頭.在權重計算中,本文采用公式來選擇當前速度盡可能低的節點.

2)節點到sink 的距離(di,sink)：由于收集的數據由簇頭進行聚合傳遞,因此更接近sink 的簇頭所消耗的能量越少.

3)剩余能量(Ei)：節點成為簇頭后會比普通節點更耗費能量,所以要考慮節點剩余能量.

4)可用信道數(Ci)：可用信道數多的節點成為簇頭,會在形成的簇中擁有更多的空閑頻譜使用機會.

5)合格節點度(Dei)：具有最多一跳合格節點鄰居數的節點更適合成為簇頭.

6)節點方向與sink 連線間夾角正切值(A)：選擇運動方向靠近sink 的節點,形成的簇更穩定.

根據這些參數,任意節點i進行簇頭選擇的權值為：

其中,w1+w2+w3+w4+w5+w6=1.在這個過程中,鄰域內權值最高的節點成為簇頭,剩余節點再次比較權值,此過程將持續到所有節點都成簇頭或者簇成員為止.

3.3 公共信道確定

每個簇頭檢查所有符合條件的單跳鄰居中是否存在公共信道.如果存在公共信道,CRSN 中的每個節點感知信道并記錄包含每個信道的PU 出現概率(Ppu)和平均信道空閑時間(Tidle)的信道狀態表.簇頭通過比較具有較低Ppu、較高Tidle和較多一跳鄰居節點的公共信道來形成簇.本文給信道a分配一個權值,它有3 個參數,公式如下：

3.4 直接分簇

完成公共信道選擇后,簇頭將向它鄰居節點發送成簇請求(Clustering REQuest,C_REQ),然而,一個節點可以是兩個或多個簇頭的鄰居,但它只能成為一個簇頭的簇成員節點.因此,節點只答復給一個簇頭.節點會計算與簇頭親密度,該值用于確定節點是否適合連接這個簇頭.該值由下面過程得出：

假設在時間t節點i的位置是：

簇頭節點j的位置是：

本文將節點接收來自一個簇頭消息的時間設置為t=0,因此有：

其中,Rtran代表節點的通信范圍.如果節點i在時間t仍在簇j中,有：

Δti,j表示節點i和節點j的估計連接時間,可以由式(8)求出,式(8)的解有兩個分別為t1、t2,如果max{t1,t2}≤0,則Δti,j=0；否則 Δti,j=max{t1,t2}.

本文在分簇時采用文獻[15]所提出了直接分簇方式.在無向分簇方式中數據傳輸需要先傳給簇頭,簇頭會聚合數據然后發給下一跳簇頭或網關,如圖5(a)所示,這會導致節點通訊開銷大,能耗高,網絡壽命短.相反,沿著數據在事件到sink 的傳播方向上分簇,這樣確保數據一直向著sink 方向傳輸而不會回傳,如圖5(b)所示.

圖5 分簇方式

其中,λ1+λ2=1.

在節點選擇完簇頭之后,它將發送一條確認信息(ACKnowledgement,ACK)來回復簇頭.如果一個非簇節點沒有收到來自相鄰簇頭的任何請求,它自己成為一個簇頭.算法2 描述了直接分簇算法,如算法2 所示.

算法2.分簇算法1：if State(j)=“CH” then a∈C j 2：for do Wa 3：calculate 4：end for 5：send C_REQ message to the nodes through channel 6：wait for ACK message from the nodes 7：else 8：if State(j)=“Eligible Node” and it receives C_REQ message then Wij a 9：calculate 10：join the cluster whose is the biggest 11：send ACK message to the selected CH j Wij 12：if State()=“Eligible Node” and it did not receive C_REQ message then j 13：State()=“CH” goto 1 14：end if 15：end if 16：end if

3.5 簇維護

由于傳感器節點的速度或方向突然變化、傳輸過程中的網絡擁塞或硬件故障造成的,因此在傳輸過程中需要加入確認消息(ACK).

在成功接收到數據包后,簇頭將向非簇頭合格節點發送ACK 消息.如果合格節點收到ACK 消息,它將確認數據包已成功傳輸,如果合格節點未收到ACK 消息它將廣播簇加入請求消息.收到簇加入聯合請求消息時,簇頭將像在第二階段那樣向該節點傳輸簇頭消息.

另外,由于簇頭節點和簇成員節點都保留了估計連接時間的信息,所以它們都可以檢查簇成員節點在下一個時隙是否會留在簇中.如果簇成員節點不打算留在簇中,它將廣播一條請求消息以加入一個新簇.然后,簇頭將刪除該簇成員節點.

圖6演示了合格節點離開舊簇并加入新簇的過程.節點5 加入簇J,而節點9 離開簇.簇J 的簇頭將節點9 從TDMA 計劃中刪除,并將節點5 添加到TDMA 計劃中.TDMA 調度是基于簇成員節點和簇頭節點之間的估計連接時間 Δt按升序排序的.新的TDMA 時間表可能具有如圖7所示的形式,節點9 被節點5 替代,而不會影響到數據傳輸.

圖6 簇維護模型圖

圖7 TDMA 時間片

4 實驗分析

本文在Matlab 2018b 中建立了一個仿真環境來研究EMC 分簇算法性能.本文主要從分簇所需要的時間,連通性和分簇過程中的能量消耗這3 個方面對協議進行了仿真測試,實驗中改變的參數是事件到sink的距離、事件區域半徑R以及節點的傳輸半徑r.本文同mESAC[9],MNB[16],EACRP[12]這3 種算法進行了比較.在模擬中,權重系數取值為w1=0.2,w2=0.1,w3=0.1,w4=0.3,w5=0.2,w6=0.1,λ1=0.8,λ2=0.2,表1為實驗中用到的參數,本次實驗的拓撲圖如圖8所示,黑點為 簇頭,灰點為簇成員.

表1 模擬參數

圖8 分簇結果拓撲圖

本文定義成功的數據包傳遞率為Rpdr,平均控制開銷為Oavg,如下所示：

其中,Nrec為 成功傳遞的數據包數目,Nlost為丟失據包,Ototal為合格區域內總控制開銷.

4.1 成簇時間

建立簇需要一些時間,時間長短取決于合格區域的建立、簇頭的選擇、節點通訊范圍等.從圖9中可以看出,mESAC,EACRP 與MNB 需要更多的分簇控制包交換,因此它們形成簇需要更多的時間.分簇所需要的時間隨著事件半徑的增加而增加,如圖10所示,EMC 分簇需要的時間相比于mESAC,EACRP 與MNB 分別提升了1.18 倍,2.81 倍和7.18 倍.

圖9 控制包數目對比圖

圖10 成簇時間對比圖

4.2 連通性分析

圖11表示了在不同傳輸半徑下,4 種算法的連通性.觀察可以看出EMC 的連通性更好,這是由于在EMC 中,采用直接分簇辦法,讓數據包沿單向傳輸,避免了數據回傳的問題,并且選擇信道數目多的節點成為簇頭,同時考慮了簇成員節點與簇頭的連接時間,減少了數據包不必要的丟失.而算法MNB、EACRP 和mESAC 沒有考慮節點連接時間,在節點離開后容易造成數據包丟失.因此EMC 的連通性相比于mESAC,EACRP 與MNB 分別提升了1.07 倍,1.63 倍和2.09 倍.

4.3 分簇能耗

CRSN 節點的電池電量有限,能耗是本文算法重點考慮的因素.通過仿真實驗得到,事件發生區域到sink 的距離和節點傳輸半徑對分簇能量的影響,節點傳輸半徑增加導致有更多的節點參與到分簇過程中,因此會消耗更多的能量.MNB 形成簇需要3 個步驟,每個節點在每一步都會通知它的鄰居節點,這會導致額外的能耗.并且MNB 和EACRP 在分簇過程中是所有節點均參加分簇,這會導致能耗必然高于EMC 和mESAC.再由圖9可以看出,mESAC 控制包的數量略高于EMC.如圖11所示,EMC 的分簇能耗同其他算法相比能耗有明顯的優勢.圖12為分簇能耗對比圖.圖13為EMC 分簇過程中簇頭能耗與節點能耗對比,簇頭能耗較高,并且節點是移動的,所以要在每一輪重新進行簇頭選擇.

圖11 連通性對比圖

圖12 分簇能耗對比圖

圖13 簇頭與節點能耗圖

5 結論

分簇是一種提高動態網絡拓撲穩定性的重要方法.針對認知無線傳感器網中移動節點能耗不均,連通性不佳的問題,本文中通過計算移動節點在合格區域的逗留時間以及節點在簇中的連接預估計時間,并采用直接分簇算法來解決移動CRSN 對于事件到sink 協調方案的問題.同時給出分簇的維護機制,通過TDMA方式來協調事件和sink 之間的通信.仿真結果表明,EMC 算法在連通性、分簇時間和分簇能耗方面均有明顯提高,能更好地適應移動場景.