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

王海峰張 利

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

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

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

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

1 節點分配約束條件

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

1.1 數據轉送路徑約束

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

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

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

1.2 節點通信容量約束

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

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

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

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

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

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

1.3 無線傳感網絡節點布局約束

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

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

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

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

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

2 無線傳感網絡節點分配算法

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

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

2.1 網格間距

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

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

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

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

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

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

2.2 無線傳感網絡節點數據轉發跳數

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

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

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

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

2.3 吞吐量

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

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

圖1 無線傳感網絡節點分配流程圖

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

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

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

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

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

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

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

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

3 仿真測試與結果

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

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

3.1 節點能耗

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

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

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

3.2 吞吐量

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

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

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

3.3 分配效果測試

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

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

圖4 無線傳感網絡節點分配結果

3.4 分配效率

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

圖5 不同算法的節點分配時間

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

4 結束語

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