考慮無線傳輸損耗的農業物聯網節點分布規劃算法研究

謝家興 梁高天 高 鵬 王衛星,3

(1.華南農業大學電子工程學院， 廣州 510642； 2.廣東省智慧果園科技創新中心， 廣州 510642；3.廣東省農情信息監測工程技術研究中心， 廣州 510642)

0 引言

在無線信號傳輸的過程中，信號不僅會隨著傳輸距離增大而衰減，還會因為地形的高低起伏而存在一定的繞射損耗[1]。然而目前農場物聯網節點的選址大多依靠經驗，沒有綜合考慮地形、信號損耗等因素，從而造成了不必要的發射功率浪費。因此設計一種合理的節點選址方法對于延長節點續航，減少電能消耗具有重大意義。

對于類似的規劃問題，常見的解決方法有蟻群算法[2]、粒子群算法[3]等群智能算法，也有Bug算法[4]、A*算法[5]、Dijkstra算法等圖搜索算法，以及聚類算法[6]等無監督學習方法。

在無線節點的選址上，文獻[7]基于基站選址優化問題的約束條件構建一種基站選址優化模型,該模型使用鯨魚優化改進算法，仿真發現算法能夠獲得更理想的優化解,且具有較快的收斂速度。文獻[8]通過把單跳Sink節點選址問題轉換為區間數學全局尋優問題,結合粒子群算法與質心理論，提出了質心重選址算法，實現了多Sink節點的最優化選址。文獻[9]將人工魚群算法應用到基站選址規劃上,提出了變步長的人工魚群算法，仿真發現該算法只需要更少的待建基站數目就能滿足覆蓋95%以上的目標。

然而目前已有文獻在節點的選址問題上很少考慮信號傳輸過程中的損耗問題，尤其是由于地形因素導致的繞射損耗，因此本文提出一種結合K-means聚類算法以及粒子群優化(Particle swarm optimization，PSO)算法的物聯網節點選址方法。該方法通過K-means算法確定每個路由的管轄終端以及初始位置，根據電磁波損耗模型建立合適的適應度函數，利用PSO算法得到路由節點的最終位置，再次使用K-means算法確定每個網關的管轄路由以及初始位置，通過PSO算法確定網關的最終位置。

1 物聯網系統概述

農場無線物聯網一般包括終端、路由以及網關3種節點，其拓撲結構如圖1所示。終端節點負責采集溫濕度等環境信息以及控制電磁閥等設備的工作；路由節點是網關與終端之間通信的橋梁，用于轉發網關對終端的下行指令以及終端到網關的上行信息，一個路由對接在它附近的多個終端；網關節點負責把終端采集到的數據通過4G等方式上傳到后臺服務器，以及接收來自服務器的控制指令并通過路由傳達給終端，一個網關對應多個路由。

圖1 農業物聯網拓撲結構Fig.1 Topology of agricultural internet of things

在農場物聯網節點的鋪設中，一般需要安裝3種節點：終端節點、路由節點與網關節點。為了方便建模，做如下假設：

(1)終端位置已知。終端需要控制電磁閥的開關與采集農情信息，它的安裝位置需要根據場地的實際情況人為決定。

(2)一個終端只能連接到一個路由，終端間不存在任何連接。需要確定每個路由所負責的終端，對終端的分割可以視為一類聚類問題。

(3)聚類中的元素一經確定后不再改變。在確定路由對接的終端后，無論路由位置如何改變，其下屬的終端都不會增加或減少。

(4)模型的目標是降低最大通信損耗。最大通信損耗指路由到多個終端或者網關到多個路由間最大的無線傳輸損耗，只要終端到其所屬的路由或者路由到網關的無線傳輸損耗小于等于最大無線傳輸損耗，即視為可以通信成功。

(5)網關只有一個，且只能與路由通信，每個路由都必須連接到網關。

2 模型建立

2.1 自由空間損耗

沒有任何障礙物的情況下電磁波在自由空間中傳播時，會存在自由空間損耗，根據國際電信聯盟(International Telecommunication Union，ITU)在2019年發布的關于自由空間損耗的參考計算方法[10]，自由空間損耗計算式為

Lfs=32.44+20lgf+20lgd

(1)

式中Lfs——自由空間損耗，dB

f——電磁波頻率，MHz

d——信號發射點與接收點的直線距離，km

2.2 繞射損耗

如果電磁波在傳輸過程中遇到凸起的障礙物，則會產生繞射損耗，根據ITU于2019年發布的關于繞射損耗的計算方法[11]，繞射損耗的計算存在2種情況，如圖2、3所示。

圖2 端點水平線在山峰下方Fig.2 Horizontal line below spike

圖3 端點水平線在山峰上方Fig.3 Horizontal line above tip

計算幾何參數的綜合量，其計算式為

(2)

式中v——全部幾何參數的綜合量，它是一個歸一化的、無量綱參數

h——端點的水平連線與峰頂的垂直距離，當端點水平線在山峰上方時(圖3)，h為負值，反之為正值(圖2)

λ——電磁波波長

d1、d2——障礙物頂部與路徑兩端間的距離

繞射損耗計算式為

(3)

式中J——繞射損耗，dB

C——復數菲涅爾積分實部

S——復數菲涅爾積分虛部

復數菲涅爾積分結果計算式為

(4)

式中Fc——復數菲涅爾積分結果

s——被積變量

為了計算方便，ITU建議在v大于-0.78時，繞射損耗J的近似值計算式為

(5)

以上僅為一種比較簡單的繞射損耗計算方式，有文獻表明在林區、丘陵、森林等不同環境中測得的繞射損耗與ITU建議公式的計算結果均有差異[12-16]，本文為了方便展示方法原理，僅使用了比較簡單的繞射損耗計算方法，在實際使用時應該根據實際的環境選擇合適的繞射損耗計算方法。

2.3 適應度模型

在本模型中，傳輸損耗的計算主要考慮的是節點發射的電磁波在傳播過程中存在的自由空間損耗以及繞射損耗，目的在于減少通信時最大傳輸損耗，所以設計路由或者網關的適應度方程式為

(6)

其中

(7)

Jp——節點p與管理節點p的終端或網關之間的繞射損耗

Ci——屬于第i個路由或網關管理的節點的集合

poslin——正值線性傳輸函數

由于傳輸損耗為非負值，當發射點與接收點距離較少時，根據式(1)計算的損耗有可能達到負無窮，為了使PSO算法正常執行，對自由空間損耗添加一個正值線性傳輸函數。

節點p不止一個，路由或者網關的最大發射功率應該高于最大傳輸損耗，故用max函數取最大的傳輸損耗作為適應度。

3 算法設計

3.1 K-means算法

K-means算法[17]是一種無監督的聚類算法，對于給定的樣本集，可以按照樣本之間的距離，將樣本劃分為k個簇。該算法用于確定路由節點的初始位置，種子與路由節點的距離采用的是平面距離，其計算方法為

(8)

式中D——種子(即終端)與路由的距離

(x1、y1)——路由坐標

(x2、y2)——終端坐標

在確定好路由的初始位置以及每個路由所負責的終端后，使用PSO算法進行位置優化。

3.2 PSO算法

PSO算法[18]是一種全局優化算法，通過群體中粒子間的合作與競爭產生的群體智能指導優化算法，它可根據對環境的適應度，將群體中的粒子移動到更好的區域，從而實現對函數全局最優的求解。

文獻[19]建議在一般情況下將個體認知分量和群體社會分量的權重設置為常數更有利于PSO算法迭代到全局最優點。為了加速PSO算法收斂，參照文獻[20]與可變學習率反向傳播(Variable learning rate back propagation)算法[21]，設計了可變慣性權重因子算法，該算法在每次迭代后都需要執行一次以獲得新的慣性權重因子，該算法的偽代碼入：全局最優點是否更新標志，目前的d值，目前的慣性權重因出：新的慣性權重因子，新的d值

Function[new_inertia, new_d] = new_inertia(flag, d, inertia)

If flag == true

new_d= max(0,d-1)

If d<2

new_inertia = inertia*2

If d>5

new_inertia = inertia/2

else

new_d =d+1

new_inertia=inertia

以上算法用變量d記錄全局最優位置不更新的次數，當d小于2時，提高慣性權重因子以提高粒子搜索最優點的能力，當全局最優位置大于5次不更新時，減少慣性權重因子以加快算法收斂。

為減少PSO執行時間，設置了最優位置不更新的最大容許時間，如果已知最優位置超過此容忍時間沒有更新時，退出PSO算法的執行，取當前最優結果作為最終優化結果。

3.3 本文算法使用步驟

本文算法使用步驟為：①對農場地形進行建模，得到地形描述函數。②根據地形描述函數，依據終端實際的分布得到終端坐標。③根據實際情況確定路由部署數量以及網關部署數量。④利用K-means聚類算法對終端進行分組，取每組的中心作為路由的初始中心。⑤針對每組終端，在該組的初始中心附近初始化若干個粒子，通過式(6)得到適應度函數，利用PSO算法確定路由的最終位置。⑥初始化若干個粒子，通過式(6)得到適應度函數，利用PSO算法確定網關的最終位置。

4 仿真分析

4.1 仿真參數

4.1.1地形描述函數

仿真使用的地形描述函數為

(-500 m≤x≤500 m,-500 m≤y≤500 m)

(9)

式中 terr(x,y)——坐標(x,y)處的地形高度

該描述函數對應地形的立體圖如圖4所示。

圖4 仿真地形立體圖Fig.4 Three-dimensional map of simulated terrain

4.1.2波長

目前大部分的物聯網節點主要工作在2.4 GHz頻段，根據電氣與電子工程師協會(Institute of Electrical and Electronics Engineers，IEEE)頒布的標準[22]，該頻段的頻率范圍為2.401～2.495 GHz，為了計算方便，采用其中心頻率f(2.448 GHz)進行仿真，則波長為

(10)

式中c——真空中的光速，取3×108m/s

可算得波長約為0.12 m。

仿真的終端數目為500個，它們的位置由系統隨機生成，分布在上述地形描述函數的定義域內。路由為5個。

4.1.3PSO算法參數

PSO算法參照文獻[23]選擇3組參數進行測試，如表1所示。

表1 PSO仿真參數Tab.1 PSO simulation parameters

為了確定PSO算法仿真最終使用的參數，進行預實驗，測試每組參數下PSO算法執行所需要的時間，每組測試5次，結果如表2所示。

表2 PSO算法不同參數組耗時測試結果Tab.2 Time-consuming test results of different parameter groups of PSO algorithm s

可見，參數組3的平均耗時顯著小于參數組1和參數組2，因此選擇參數組3作為PSO算法的參數。

設置PSO算法粒子最大遷移次數為400次；最小容忍遷移距離為10-6m；最優位置不更新的最大容許時間為120 s。當滿足以下條件之一時結束PSO算法：①遷移達到400次。②所有的粒子遷移距離小于最小容忍距離。③群體最優位置超過120 s沒有更新。

4.2 仿真結果

4.2.1分類

對隨機初始化的500個終端使用K-means算法分成5類，結果如圖5所示。

圖5 K-means分類結果Fig.5 K-means classification results

圖5中處在同一聚類中的終端用同一種顏色表示，可見分類結果有明顯的分類邊界。因為K-means算法存在一定的隨機性，所以將該算法運行了10次，取最好的一次進行繪圖以及下一步的分析。

4.2.2路由位置優化

使用PSO算法，在圖5的聚類中心附近初始化20個粒子，執行算法進行路由位置擇優，優化結果如圖6所示。

圖6 路由位置優化結果Fig.6 Route location optimization results

優化前后各個路由的最大傳輸損耗如表3所示。可見，通過PSO算法的位置優化，5個路由最大傳輸損耗均得到了減少，其中路由4的最大傳輸損耗減少率達到了27.82%。

表3 PSO算法位置尋優結果比較Tab.3 Comparison of PSO algorithm location optimization results

4.2.3網關位置確定

使用PSO算法確定網關位置，先求出到5個路由距離和最小的點，在此點附近初始化20個粒子，執行優化算法，結果如圖7所示。優化前后網關的最大傳輸損耗分別為90.91 dB和89.66 dB，通過優化，最大傳輸損耗降低了1.37%。

圖7 網關的位置Fig.7 Location of gateway

5 實地檢驗

為了驗證算法的有效性，選取華南農業大學園藝教學實驗基地作為測試場地，其俯視圖如圖8所示。

圖8 實驗場地俯視圖(航拍)Fig.8 Top view of experimental site (aerial photography)

5.1 地形建模與通信質量分析

圖9 地形采樣儀Fig.9 Terrain sampler

為了得到場地的地形情況以便建模分析，自主設計了一款地形采集裝置，該裝置實物如圖9所示，采用RadioLink公司生產的“SE100”GPS定位器獲取樣點的經緯度，利用GoerTek公司的“SPL06-001”數字大氣壓力傳感器得到樣點的高度信息。

地形信息采樣后，為了對地形進行分析，取所有樣點經緯度的中心為原點，建立直角坐標系，并根據采樣點的經緯度得到每個點相對于原點的坐標(x,y)，通過最鄰近插值法對地形做數字化建模分析，樣點以及建模結果如圖 10所示，其中藍色點為用于地形建模的轉換后采樣點，曲面為對實驗場地進行插值建模的結果，曲面的顏色表示地勢高度。

圖10 地形采樣點以及地形建模結果Fig.10 Terrain sampling points and terrain modeling results

物聯網通信模擬測試采用TI公司的CC2530芯片作為信號收發端，使用同一公司旗下的CC2591芯片作為信號功率放大器，通過CC2530芯片接收數據包時返回的接收信號強度指標(Received signal-strength indication，RSSI)評判通信質量,RSSI值越大表示通信質量越好。在實地測試時，把RSSI回傳至上述自制地形采樣儀，從而得到對應GPS坐標位置的信號強度。

5.2 實驗過程與結果

受到實際情況限制，在實地驗證時只使用5個終端與1個路由器節點，終端安裝到指定位置，實驗人員手持采樣儀，在算法分析得到的最優點及其附近測量RSSI值，從而驗證算法結果的有效性。終端GPS坐標以及算法給出的最佳路由位置如表4所示。

表4 終端與路由的坐標Tab.4 Coordinates of terminal and route

在算法推薦的最優點及其附近，采集路由分別到5個終端的RSSI，共采樣160個點，其中最優點及其東南西北2 m處的采樣結果如表5所示。

表5 部分測量點RSSI數據Tab.5 RSSI data of some measuring points

可見，最優點到5個終端RSSI的最小值均比其附近的點大，最優點的最小RSSI相比其附近的點提升了12%～20%，說明本文算法可提高無線通信質量。

6 結論

(1)在考慮無線傳輸損耗的基礎上，提出了一種基于K-means聚類算法與PSO算法的農場物聯網規劃算法，該算法首先對農場建模得到地形描述函數，通過已經部署好的終端的坐標，利用K-means算法得到路由的管轄終端與大概的位置，在考慮地形因素對節點間信號傳輸影響的前提下，建立了以自由空間損耗和繞射損耗最小化為目標的數學模型，結合PSO算法得到路由和網關的安裝位置。

(2)仿真分析發現，該算法有助于為路由與網關的鋪設位置提供參考建議，使用PSO算法可以顯著降低最大傳輸損耗，最大減少率為27.82%。實地檢驗發現，本算法所選取的最優點通信質量顯著高于其附近的點，RSSI提升了12%～20%。

(3)對于地表覆蓋物的不同，繞射損耗的實際值與ITU推薦的理論值有差別，因此在實際應用中，應根據地表覆蓋物的種類對繞射損耗的計算方法進行改進。