考慮節(jié)點間距的無線傳感網絡節(jié)點分配算法*

王海峰張 利

(1.南通職業(yè)大學電子信息工程學院，江蘇 南通 226007；2.西華大學經濟學院，四川 成都 610039)

無線傳感網絡在實際運行過程的依據是合理的節(jié)點分配[1-2]，網關節(jié)點通常情況下會決定節(jié)點在無線傳感網絡中的位置。合理分配無線傳感網絡節(jié)點可以提高其在運行過程中的連通性和可靠性，節(jié)點分配結果同時也決定了無線傳感網絡的通信效率和壽命等指標，對無線傳感網絡節(jié)點分配具有重要意義。

李道全等[3]在提出了基于蟻群算法、擬物力和質心算法的無線傳感網絡節(jié)點分布優(yōu)化策略。利用蟻群算法選取無線傳感網絡節(jié)點個數和位置后，運用擬物力算法優(yōu)化選中的節(jié)點，并采用質心算法提高節(jié)點定位精度，但是該方法存在節(jié)點能耗高、吞吐量低的問題。Karimi-Bidhendi S等[4]研究了一種異構雙層無線傳感器網絡，該異構節(jié)點部署問題被建模為一個以網絡總功耗為代價函數的優(yōu)化問題，解決了通信范圍受限時的傳感器部署問題，但是該方法存在節(jié)點能耗高、分配效率低的問題。蔣勇等[5]根據節(jié)點的成本屬性、服務能力和最大服務半徑構建節(jié)點布局優(yōu)化模型，采用和聲搜索算法對模型求解，完成節(jié)點分配，但是該方法沒有考慮節(jié)點在無線傳感網絡中的間隔，存在分配效果差和分配效率低的問題。

為了解決上述問題，在考慮節(jié)點間距的基礎上，以吞吐量為前提，優(yōu)化無線傳感網絡通信鏈路，實現節(jié)點分配。本文的主要研究思路為:首先確定無線傳感網絡通信節(jié)點分配多個方面的約束條件，在此基礎上利用網格路由方法實現節(jié)點分配，最后通過仿真測試驗證此次方法的有效性。

1 節(jié)點分配約束條件

無線傳感器網絡中，節(jié)點數量往往成百上千，并且大多數節(jié)點都是隨機分布的，而應用環(huán)境經常是管理人員難以進入的區(qū)域，因此很難預先布置好每個節(jié)點的位置，這無疑加大了節(jié)點定位的難度。同時，為了盡可能地降低節(jié)點間的通信開銷，延長整個網絡的生命周期，本文在考慮節(jié)點間距的基礎上，從數據轉送路徑、節(jié)點通信容量、節(jié)點布局三個方面設定約束條件。

1.1 數據轉送路徑約束

不同類型節(jié)點在通信網絡中的通信能力是數據轉送路徑中的主要約束條件[6-7]，即節(jié)點在無線傳感網絡中的有效通信半徑。在無線傳感網絡節(jié)點分配過程中，應該保證任意一個節(jié)點經過中繼節(jié)點可以到達網關節(jié)點，在傳播過程中不存在逆向傳播方向，即從無線傳感網絡節(jié)點到網關節(jié)點的傳送路徑只存在唯一的方向，設Re＿dir＿1、Re＿dir＿2、Re＿dir＿3表示不可逆判斷因子，其計算公式如下:

式中:＜SNi，RNj＞表示無線傳感網絡節(jié)點SNi與網絡中相鄰中繼節(jié)點RNj的坐標向量；＜SNi，GN＞表示無線傳感網絡節(jié)點SNi至網關節(jié)點GN的坐標向量，該向量屬于基準向量，可以判斷數據轉送路徑的不可逆；＜RNi，RNj＞表示兩個任意相鄰中繼節(jié)點RNi、RNj之間在數據轉送路徑中的坐標向量；＜RNi，GN＞表示最后一個中繼節(jié)點RNi至網關節(jié)點GN在數據轉送路徑上的坐標向量。

通過式(1)計算得到的不可逆因子Re＿dir＿1、Re＿dir＿2、Re＿dir＿3判斷數據轉送路徑是否符合不可逆判斷條件，通過判斷結果可以保證無線傳感網絡節(jié)點分配完成后，中繼節(jié)點與網關節(jié)點之間存在最短路徑和最少無線傳感網絡節(jié)點。

1.2 節(jié)點通信容量約束

如果節(jié)點在無線傳感網絡中存在過重的任務，即無線傳感網絡節(jié)點在無線傳感網絡中的數據傳輸率較高，會對無線傳感網絡的整體可靠性產生影響[8-9]。因此需要約束無線傳感網絡節(jié)點在無線傳感網絡中的數據傳送率βi:

式中:αj表示起始無線傳感網絡節(jié)點在數據傳輸路徑中對應的數據發(fā)信率。

確定無線傳感網絡節(jié)點的分配位置時，需要考慮中繼節(jié)點與無線傳感網絡節(jié)點之間存在的通信距離，同時需要考慮不同通信距離范圍中存在的中繼節(jié)點，以此為基礎，獲得無線傳感網絡的候選通信路徑[10-11]。

設X1和X2表示無線傳感網絡節(jié)點SN1的兩條路徑，X3和X4表示無線傳感網絡節(jié)點SN2的兩條路徑，“1”表示選中某條數據傳輸路徑，“0”表示數據傳輸路徑沒有被選中。無線傳感網絡完成布設后，節(jié)點在無線傳感網絡中運行時必然會選擇一條路徑傳輸數據，因此存在式(3):

根據上述傳輸路徑中中繼節(jié)點RN自身的通信容量，設置約束條件如式(4):

式中:β1、β2、β3表示中繼節(jié)點RN1、RN2、RN3對應的數據傳送率；αi表示無線傳感網絡節(jié)點傳輸數據的發(fā)信率；γi表示中繼節(jié)點RN1、RN2、RN3對應的數據轉送率最大值。

1.3 無線傳感網絡節(jié)點布局約束

傳感器發(fā)送節(jié)點在無線傳感網絡中與傳感器接收節(jié)點之間存在的功率關系為式(5):

式中:PR、PT分別表示節(jié)點在無線傳感網絡中的接收功率和發(fā)送功率；GT、GR分別表示接收天線和發(fā)射天線在無線傳感網絡中對應的增益；λ表示無線信號媒介對應的波長；d表示收發(fā)節(jié)點在無線傳感網絡中的間距；L表示損耗因子，通常情況下不受無線傳播的影響。

設P0表示無線傳感網絡節(jié)點可以接收并正確解碼信號的最小功率，當節(jié)點功率PR＝P0時，在無線傳感網絡中的最小發(fā)送功率PTm為式(6):

分析式(6)可知，無線傳感網絡節(jié)點的傳輸距離與發(fā)送功率之間成正比關系。

設dis＿fac表示通信網絡距離因子，其表達式如式(7):

2 無線傳感網絡節(jié)點分配算法

考慮節(jié)點間距的無線傳感網絡節(jié)點分配算法利用網格路由方法實現無線傳感網絡節(jié)點分配。

利用網格路由方式劃分無線傳感網絡監(jiān)測區(qū)域，獲得二維網格。網格路由可以提高無線傳感網絡數據傳輸的可靠性，避免因節(jié)點失效和包丟失產生的故障問題，因此所提算法在網格的交叉點上分配無線傳感網絡節(jié)點。

2.1 網格間距

根據網格間距劃分無線傳感網絡監(jiān)測區(qū)域。當網格相鄰節(jié)點間距過大導致無法提供通信時，網格中的相鄰節(jié)點容易發(fā)生數據轉發(fā)和數據包丟失。此時，無線傳感網絡中節(jié)點之間的通信可以通過增加無線傳感網絡中傳感器發(fā)射功率實現通信，但這一過程會增加節(jié)點的能量消耗；當網格相鄰節(jié)點間距過小時，會增加無線傳感網絡節(jié)點到sink節(jié)點的數據轉發(fā)跳數，并且所選節(jié)點的數量也隨之增加，存在能耗較高的問題。通過上述分析可知，分配無線傳感網絡節(jié)點時需要設定合理的網格間距[12-13]。

考慮節(jié)點間距的無線傳感網絡節(jié)點分配算法通過鏈路質量指示和接收信號強度指示器設置網格間距。

無線傳感網絡接收機和發(fā)射機之間的距離可以通過測量射頻信號的能量計算，接收功率與發(fā)射功率之間的關系如式(8):

式中:n表示無線傳感網絡的傳播因子；PT、PR分別表示無線信號在無線傳感網絡中的發(fā)射功率和接收功率；d表示接收機和發(fā)射機之間在無線傳感網絡中的距離。

為了實現數據在無線傳感網絡中的傳輸，需要保障無線傳感網絡節(jié)點與中繼節(jié)點之間的通信，因此網格間距通常情況下需要符合下式:

式中:L、R均表示網格距離參數。

2.2 無線傳感網絡節(jié)點數據轉發(fā)跳數

設si和s0表示網格中的節(jié)點，其對應的坐標為

如果點si在垂直方向或水平方向轉發(fā)數據，需要布置較多的無線傳感網絡節(jié)點，此時能耗較高，用描述點si和s0轉發(fā)數據時對應的最大跳數；當點si在sis0方向轉發(fā)數據時，需要較少的傳感器數量，此時能耗較低，用描述點s和s轉發(fā)數據時對應的最大i0跳數。

根據上述分析，利用式(10)設置無線傳感網絡節(jié)點到sink節(jié)點的最大數據轉發(fā)跳數hop＿cpunt＿max(si，s0):

式中:d(si，s0)表示點si和s0之間存在的距離。

2.3 吞吐量

在分配無線傳感網絡節(jié)點時，必須考慮節(jié)點在數據傳輸期間的吞吐量。選擇通信節(jié)點路徑過程中應基于以下標準:

根據上述分析，采用貪婪算法實現無線傳感網絡節(jié)點的分配，具體過程如圖1所示。

圖1 無線傳感網絡節(jié)點分配流程圖

圖1所示的無線傳感網絡節(jié)點分配過程為:

步驟1:初始化節(jié)點k＝0，并輸入節(jié)點位置、通信半徑和網格間距等基礎信息；

步驟2:計算傳感器節(jié)點與sink節(jié)點之間的距離，并按照距離降序進行排列；

步驟3:以排列后的節(jié)點順序為基礎，構建傳感器節(jié)點集合；

步驟4:使得k＝k＋1，并判斷傳感器節(jié)點和sink節(jié)點距離是否小于通信距離，如果是，結束節(jié)點分配，如果不是，執(zhí)行步驟5；

步驟5:在通信范圍內搜索中繼節(jié)點，并選擇下一跳節(jié)點；

步驟6:根據最近貪婪準則選擇下一跳，直至達到sink節(jié)點；

步驟7:判斷選擇的k是否等于最大節(jié)點數量n，如果是，完成節(jié)點分配，如果不是，返回步驟3，重復步驟4～7，直至完成節(jié)點分配。

3 仿真測試與結果

為了驗證考慮節(jié)點間距的無線傳感網絡節(jié)點分配算法的整體有效性，需要對所提算法進行測試。

在半徑為40 m的圓形范圍內任意安置200個傳感器節(jié)點，簇節(jié)點處于圓形范圍的中心位置。仿真運行過程中，傳感器節(jié)點每隔4 s收集相應的數據，并將檢查數據信息傳遞給其他節(jié)點。通過對比所提算法分配前后的節(jié)點能耗、吞吐量以及分配效果，以及所提算法與文獻[3]算法和文獻[4]算法的分配效率，驗證所提算法的優(yōu)越性。仿真場景設置參數如表1所示。

3.1 節(jié)點能耗

采用考慮節(jié)點間距的無線傳感網絡節(jié)點分配算法分配節(jié)點，對比分配前后的節(jié)點能耗，測試結果如圖2所示。

根據圖2中的數據可知，采用所提算法分配無線傳感網絡節(jié)點后，與分配前相比，節(jié)點能耗顯著下降，最高能耗為2.8×10-11W，表明所提算法，在節(jié)點數據傳輸過程中，考慮了相鄰節(jié)點間距對能耗的影響，并將吞吐量作為傳輸前提條件，優(yōu)化了節(jié)點的能耗。

圖2 分配前后無線傳感網絡節(jié)點能耗變化

3.2 吞吐量

當吞吐量一致時，最大跳數越高，節(jié)點傳輸數據的能力越好，利用無線傳感網絡對同一組數據進行傳輸，對比節(jié)點分配前后傳輸數據的最大跳數，測試結果如圖3所示。

圖3 分配前后最大跳數測試結果

分析圖3可知，采用考慮節(jié)點間距的無線傳感網絡節(jié)點分配算法對節(jié)點分配后，在無線傳感網絡中傳輸吞吐量一致的相同數據時，所用的最大跳數明顯減少，分配后最大跳數為2，相較于分配前降低了較高的跳數，由此可知，所提算法可用較少的節(jié)點傳輸相同的數據，表明用所提算法對節(jié)點進行分配后，節(jié)點的吞吐量得以提高。

3.3 分配效果測試

采用考慮節(jié)點間距的無線傳感網絡節(jié)點分配算法對節(jié)點進行分配，測試所提算法的分配效果。

圖4中的黑色方塊，表明節(jié)點存在重復，分析圖4(a)可知，原始無線傳感網絡中存在大量的節(jié)點重復，采用所提算法分配無線傳感網絡節(jié)點后，結果如圖4(b)所示，根據圖4(b)可知，采用所提算法對無線傳感網絡節(jié)點分配后，無線傳感網絡中不存在重復的節(jié)點，表明所提算法的無線傳感網絡節(jié)點分配效果好，因為所提算法對節(jié)點分配時，考慮了節(jié)點在網格中的間距，避免了節(jié)點重復問題。

圖4 無線傳感網絡節(jié)點分配結果

3.4 分配效率

為了進一步驗證所提算法的整體有效性，將文獻[3]算法和文獻[4]算法與所提算法進行對比測試，測試上述算法分配無線傳感網絡節(jié)點所用的時間，測試結果如圖5所示。

圖5 不同算法的節(jié)點分配時間

分析圖5可知，在多次迭代中所提算法分配節(jié)點所用的時間遠低于文獻[3]算法和文獻[4]算法分配節(jié)點所用的時間，最高時間為0.62 min，驗證了所提算法具有較高的節(jié)點分配效率。

4 結束語

無線傳感網絡被廣泛地應用在各個領域中進行數據監(jiān)測，其中的無線傳感網絡節(jié)點具有采集、傳輸、處理數據的功能，然而在特殊或復雜環(huán)境下難以補充無線傳感網絡節(jié)點的能量，因此研究無線傳感網絡節(jié)點的分配算法有利于降低節(jié)點能耗。目前無線傳感網絡節(jié)點分配算法存在節(jié)點能耗高、吞吐量低、布局效果差和分配效率低的問題。為此，在考慮節(jié)點間距的前提下，研究了無線傳感網絡節(jié)點分配算法，通過網格間距、無線傳感網絡節(jié)點數據轉發(fā)跳數、吞吐量、節(jié)點分配四方面的約束和優(yōu)化，實現了無線傳感網絡節(jié)點分配，仿真結果表明，該算法可有效地解決目前算法中存在的問題，為無線傳感網絡的運行提供了保障。