謝家興 梁高天 高 鵬 王衛(wèi)星,3

(1.華南農(nóng)業(yè)大學(xué)電子工程學(xué)院， 廣州 510642； 2.廣東省智慧果園科技創(chuàng)新中心， 廣州 510642；3.廣東省農(nóng)情信息監(jiān)測工程技術(shù)研究中心， 廣州 510642)

0 引言

在無線信號傳輸?shù)倪^程中，信號不僅會隨著傳輸距離增大而衰減，還會因?yàn)榈匦蔚母叩推鸱嬖谝欢ǖ睦@射損耗[1]。然而目前農(nóng)場物聯(lián)網(wǎng)節(jié)點(diǎn)的選址大多依靠經(jīng)驗(yàn)，沒有綜合考慮地形、信號損耗等因素，從而造成了不必要的發(fā)射功率浪費(fèi)。因此設(shè)計(jì)一種合理的節(jié)點(diǎn)選址方法對于延長節(jié)點(diǎn)續(xù)航，減少電能消耗具有重大意義。

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

在無線節(jié)點(diǎn)的選址上，文獻(xiàn)[7]基于基站選址優(yōu)化問題的約束條件構(gòu)建一種基站選址優(yōu)化模型,該模型使用鯨魚優(yōu)化改進(jìn)算法，仿真發(fā)現(xiàn)算法能夠獲得更理想的優(yōu)化解,且具有較快的收斂速度。文獻(xiàn)[8]通過把單跳Sink節(jié)點(diǎn)選址問題轉(zhuǎn)換為區(qū)間數(shù)學(xué)全局尋優(yōu)問題,結(jié)合粒子群算法與質(zhì)心理論，提出了質(zhì)心重選址算法，實(shí)現(xiàn)了多Sink節(jié)點(diǎn)的最優(yōu)化選址。文獻(xiàn)[9]將人工魚群算法應(yīng)用到基站選址規(guī)劃上,提出了變步長的人工魚群算法，仿真發(fā)現(xiàn)該算法只需要更少的待建基站數(shù)目就能滿足覆蓋95%以上的目標(biāo)。

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

1 物聯(lián)網(wǎng)系統(tǒng)概述

農(nóng)場無線物聯(lián)網(wǎng)一般包括終端、路由以及網(wǎng)關(guān)3種節(jié)點(diǎn)，其拓?fù)浣Y(jié)構(gòu)如圖1所示。終端節(jié)點(diǎn)負(fù)責(zé)采集溫濕度等環(huán)境信息以及控制電磁閥等設(shè)備的工作；路由節(jié)點(diǎn)是網(wǎng)關(guān)與終端之間通信的橋梁，用于轉(zhuǎn)發(fā)網(wǎng)關(guān)對終端的下行指令以及終端到網(wǎng)關(guān)的上行信息，一個路由對接在它附近的多個終端；網(wǎng)關(guān)節(jié)點(diǎn)負(fù)責(zé)把終端采集到的數(shù)據(jù)通過4G等方式上傳到后臺服務(wù)器，以及接收來自服務(wù)器的控制指令并通過路由傳達(dá)給終端，一個網(wǎng)關(guān)對應(yīng)多個路由。

圖1 農(nóng)業(yè)物聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)Fig.1 Topology of agricultural internet of things

在農(nóng)場物聯(lián)網(wǎng)節(jié)點(diǎn)的鋪設(shè)中，一般需要安裝3種節(jié)點(diǎn)：終端節(jié)點(diǎn)、路由節(jié)點(diǎn)與網(wǎng)關(guān)節(jié)點(diǎn)。為了方便建模，做如下假設(shè)：

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

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

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

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

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

2 模型建立

2.1 自由空間損耗

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

Lfs=32.44+20lgf+20lgd

(1)

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

f——電磁波頻率，MHz

d——信號發(fā)射點(diǎn)與接收點(diǎn)的直線距離，km

2.2 繞射損耗

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

圖2 端點(diǎn)水平線在山峰下方Fig.2 Horizontal line below spike

圖3 端點(diǎn)水平線在山峰上方Fig.3 Horizontal line above tip

計(jì)算幾何參數(shù)的綜合量，其計(jì)算式為

(2)

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

h——端點(diǎn)的水平連線與峰頂?shù)拇怪本嚯x，當(dāng)端點(diǎn)水平線在山峰上方時(shí)(圖3)，h為負(fù)值，反之為正值(圖2)

λ——電磁波波長

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

繞射損耗計(jì)算式為

(3)

式中J——繞射損耗，dB

C——復(fù)數(shù)菲涅爾積分實(shí)部

S——復(fù)數(shù)菲涅爾積分虛部

復(fù)數(shù)菲涅爾積分結(jié)果計(jì)算式為

(4)

式中Fc——復(fù)數(shù)菲涅爾積分結(jié)果

s——被積變量

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

(5)

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

2.3 適應(yīng)度模型

在本模型中，傳輸損耗的計(jì)算主要考慮的是節(jié)點(diǎn)發(fā)射的電磁波在傳播過程中存在的自由空間損耗以及繞射損耗，目的在于減少通信時(shí)最大傳輸損耗，所以設(shè)計(jì)路由或者網(wǎng)關(guān)的適應(yīng)度方程式為

(6)

其中

(7)

Jp——節(jié)點(diǎn)p與管理節(jié)點(diǎn)p的終端或網(wǎng)關(guān)之間的繞射損耗

Ci——屬于第i個路由或網(wǎng)關(guān)管理的節(jié)點(diǎn)的集合

poslin——正值線性傳輸函數(shù)

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

節(jié)點(diǎn)p不止一個，路由或者網(wǎng)關(guān)的最大發(fā)射功率應(yīng)該高于最大傳輸損耗，故用max函數(shù)取最大的傳輸損耗作為適應(yīng)度。

3 算法設(shè)計(jì)

3.1 K-means算法

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

(8)

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

(x1、y1)——路由坐標(biāo)

(x2、y2)——終端坐標(biāo)

在確定好路由的初始位置以及每個路由所負(fù)責(zé)的終端后，使用PSO算法進(jìn)行位置優(yōu)化。

3.2 PSO算法

PSO算法[18]是一種全局優(yōu)化算法，通過群體中粒子間的合作與競爭產(chǎn)生的群體智能指導(dǎo)優(yōu)化算法，它可根據(jù)對環(huán)境的適應(yīng)度，將群體中的粒子移動到更好的區(qū)域，從而實(shí)現(xiàn)對函數(shù)全局最優(yōu)的求解。

文獻(xiàn)[19]建議在一般情況下將個體認(rèn)知分量和群體社會分量的權(quán)重設(shè)置為常數(shù)更有利于PSO算法迭代到全局最優(yōu)點(diǎn)。為了加速PSO算法收斂，參照文獻(xiàn)[20]與可變學(xué)習(xí)率反向傳播(Variable learning rate back propagation)算法[21]，設(shè)計(jì)了可變慣性權(quán)重因子算法，該算法在每次迭代后都需要執(zhí)行一次以獲得新的慣性權(quán)重因子，該算法的偽代碼入：全局最優(yōu)點(diǎn)是否更新標(biāo)志，目前的d值，目前的慣性權(quán)重因出：新的慣性權(quán)重因子，新的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記錄全局最優(yōu)位置不更新的次數(shù)，當(dāng)d小于2時(shí)，提高慣性權(quán)重因子以提高粒子搜索最優(yōu)點(diǎn)的能力，當(dāng)全局最優(yōu)位置大于5次不更新時(shí)，減少慣性權(quán)重因子以加快算法收斂。

為減少PSO執(zhí)行時(shí)間，設(shè)置了最優(yōu)位置不更新的最大容許時(shí)間，如果已知最優(yōu)位置超過此容忍時(shí)間沒有更新時(shí)，退出PSO算法的執(zhí)行，取當(dāng)前最優(yōu)結(jié)果作為最終優(yōu)化結(jié)果。

3.3 本文算法使用步驟

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

4 仿真分析

4.1 仿真參數(shù)

4.1.1地形描述函數(shù)

仿真使用的地形描述函數(shù)為

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

(9)

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

該描述函數(shù)對應(yīng)地形的立體圖如圖4所示。

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

4.1.2波長

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

(10)

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

可算得波長約為0.12 m。

仿真的終端數(shù)目為500個，它們的位置由系統(tǒng)隨機(jī)生成，分布在上述地形描述函數(shù)的定義域內(nèi)。路由為5個。

4.1.3PSO算法參數(shù)

PSO算法參照文獻(xiàn)[23]選擇3組參數(shù)進(jìn)行測試，如表1所示。

表1 PSO仿真參數(shù)Tab.1 PSO simulation parameters

為了確定PSO算法仿真最終使用的參數(shù)，進(jìn)行預(yù)實(shí)驗(yàn)，測試每組參數(shù)下PSO算法執(zhí)行所需要的時(shí)間，每組測試5次，結(jié)果如表2所示。

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

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

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

4.2 仿真結(jié)果

4.2.1分類

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

圖5 K-means分類結(jié)果Fig.5 K-means classification results

圖5中處在同一聚類中的終端用同一種顏色表示，可見分類結(jié)果有明顯的分類邊界。因?yàn)镵-means算法存在一定的隨機(jī)性，所以將該算法運(yùn)行了10次，取最好的一次進(jìn)行繪圖以及下一步的分析。

4.2.2路由位置優(yōu)化

使用PSO算法，在圖5的聚類中心附近初始化20個粒子，執(zhí)行算法進(jìn)行路由位置擇優(yōu)，優(yōu)化結(jié)果如圖6所示。

圖6 路由位置優(yōu)化結(jié)果Fig.6 Route location optimization results

優(yōu)化前后各個路由的最大傳輸損耗如表3所示?？梢姡ㄟ^PSO算法的位置優(yōu)化，5個路由最大傳輸損耗均得到了減少，其中路由4的最大傳輸損耗減少率達(dá)到了27.82%。

表3 PSO算法位置尋優(yōu)結(jié)果比較Tab.3 Comparison of PSO algorithm location optimization results

4.2.3網(wǎng)關(guān)位置確定

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

圖7 網(wǎng)關(guān)的位置Fig.7 Location of gateway

5 實(shí)地檢驗(yàn)

為了驗(yàn)證算法的有效性，選取華南農(nóng)業(yè)大學(xué)園藝教學(xué)實(shí)驗(yàn)基地作為測試場地，其俯視圖如圖8所示。

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

5.1 地形建模與通信質(zhì)量分析

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

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

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

圖10 地形采樣點(diǎn)以及地形建模結(jié)果Fig.10 Terrain sampling points and terrain modeling results

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

5.2 實(shí)驗(yàn)過程與結(jié)果

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

表4 終端與路由的坐標(biāo)Tab.4 Coordinates of terminal and route

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

表5 部分測量點(diǎn)RSSI數(shù)據(jù)Tab.5 RSSI data of some measuring points

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

6 結(jié)論

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

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

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