基于煙花爆炸式混合蛙跳算法的LoRa網(wǎng)絡(luò)參數(shù)分配策略*

周 超，章 輝，楊茂恒，鄭天宇，姜美君

(南開大學(xué) 天津市光電傳感器與傳感網(wǎng)絡(luò)技術(shù)重點實驗室，天津 300350)

0 引 言

隨著物聯(lián)網(wǎng)(Internet of Things，IoT)的發(fā)展，網(wǎng)絡(luò)需要承載的終端設(shè)備數(shù)量呈指數(shù)級遞增，許多新興的物聯(lián)網(wǎng)技術(shù)方案逐步出現(xiàn)[1]，其中低功耗廣域網(wǎng)(Low-Power Wide-Area Network，LPWAN)憑借超低的功耗和較低的組網(wǎng)成本實現(xiàn)超遠(yuǎn)距離傳輸，受到了廣泛關(guān)注。而作為眾多LPWAN技術(shù)中的一員，LoRaWAN以其組網(wǎng)簡單靈活、可在免許可頻段使用以及能夠以極低的功耗進(jìn)行遠(yuǎn)程通信等優(yōu)點，被認(rèn)為是當(dāng)今最有前景的低功耗廣域網(wǎng)技術(shù)之一[2]。

LoRaWAN采用星型拓?fù)浣Y(jié)構(gòu)[3]，該星型拓?fù)溆删W(wǎng)關(guān)和多個LoRa終端節(jié)點互連組成。原則上，每個節(jié)點都可以選擇網(wǎng)關(guān)能正確接收的最小擴(kuò)頻因子(Spreading Factor，SF)進(jìn)行通信，這也是當(dāng)前在LoRaWAN中使用的自適應(yīng)速率策略(Adaptive Data Rate，ADR)的目標(biāo)[4]。但是，隨著 LoRa技術(shù)的普及，在相近的區(qū)域內(nèi)存在許多LoRa終端，在終端正常傳輸?shù)臅r候，各個終端之間勢必會出現(xiàn)干擾問題，大量終端同時請求發(fā)起通信也會導(dǎo)致信道擁塞、傳輸質(zhì)量下降等問題。目前一些研究主要聚焦在LoRa系統(tǒng)的性能和系統(tǒng)可擴(kuò)展性分析等問題上[5-12]，LoRa設(shè)備的性能不僅取決于通信技術(shù)，還取決于網(wǎng)關(guān)如何管理無線資源。

混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)最初由Eusuff[13]在2006年提出，算法模擬青蛙群體在濕地上跳動覓食的行為，通過青蛙個體間的合作與競爭實現(xiàn)在多維空間中對最優(yōu)解的搜索。但混合蛙跳算法與上文提及的遺傳算法、粒子群算法等在進(jìn)行求解時都存在著傳統(tǒng)群體智能算法通有的易陷入局部最優(yōu)解、收斂精度低等缺陷?；诖耍疚奶岢隽艘环N基于煙花爆炸式混合蛙跳算法的LoRa網(wǎng)絡(luò)資源分配策略。首先，對混合蛙跳算法引入反向?qū)W習(xí)、自適應(yīng)煙花爆炸、高斯變異算子和歐氏距離分配種群等機(jī)制，提高算法的搜索性能；其次，將帶有約束系數(shù)的平均傳輸成功率作為適應(yīng)度函數(shù)，保證節(jié)點在數(shù)據(jù)可達(dá)網(wǎng)關(guān)的同時分配最佳參數(shù)，從而獲得更好的可靠性；最后，使用基于LoRaSim的仿真平臺對分配好的節(jié)點參數(shù)進(jìn)行測試。實驗結(jié)果表明本文算法優(yōu)于其他算法，相較于其他算法具有更好的收斂精度，同時相較于傳統(tǒng)ADR策略顯著提升了信息接收率，能顯著降低節(jié)點傳輸過程中的碰撞概率。

1 問題描述及模型

1.1 LoRa接收特性

LoRa技術(shù)在我國主要工作在433 MHz和470 MHz頻段，在歐美等國家主要工作在868 MHz和915 MHz頻段[14]。帶寬主要使用125 kHz、250 kHz和500 kHz，傳輸速率可達(dá)0.1～120 kb/s，實際傳輸速率受每個節(jié)點的擴(kuò)頻因子、帶寬和編碼率等參數(shù)的限制，具體計算方式如下：

(1)

式中：SF表示擴(kuò)展因子，BW表示帶寬，CR表示編碼率。

LoRa數(shù)據(jù)包傳輸時間Ts由有效負(fù)載的傳輸時間和前導(dǎo)碼的傳輸時間組成[11]，其中發(fā)送單個符號所需的時間Tsym表示如下：

Rs=BW/2SF，

(2)

Tsym=1/Rs。

(3)

式中：Rs為符號速率。前導(dǎo)碼傳輸時間Tpreamble為

Tpreamble=(npreamble+4.25)·Tsym。

(4)

式中：npreamble為前導(dǎo)碼的長度，有效負(fù)載需要的傳輸時間Tpayload為

payload=8+max(ceil((8PL-4SF+28+16-20H)/

(4(SF-2DE)))(CR+4),0) ，

(5)

Tpayload=payload·Tsym。

(6)

式中：payload為有效負(fù)載的符號數(shù)，PL為有效負(fù)載的長度，H表示選擇的報頭類型，DE表示數(shù)據(jù)傳輸過程中是否采用低速率優(yōu)化，ceil為取整函數(shù)。最終數(shù)據(jù)包傳輸時間為

Ts=Tpayload+Tpreamble。

(7)

信號接收強(qiáng)度Pr(d)可根據(jù)發(fā)射功率Ptx和天線增益G得到

Pr(d)=Ptx+G-Lp(d) 。

(8)

根據(jù)LoRa網(wǎng)絡(luò)的應(yīng)用場景和大規(guī)模部署的特點，本文使用對數(shù)路徑損耗模型：

(9)

式中：d是從終端節(jié)點到網(wǎng)關(guān)的距離，d0是參考距離，Lp(d0) 是參考距離處的路徑損耗，γ是路徑損耗指數(shù)，Xσ是服從均值為0標(biāo)準(zhǔn)差為δ的正態(tài)分布。

1.2 碰撞分析

LoRa終端節(jié)點采用了一種基于ALOHA的協(xié)議進(jìn)行傳輸，只要LoRa終端產(chǎn)生信息就會盡量發(fā)送。雖然這種傳輸協(xié)議簡單易實現(xiàn)，但同樣存在很多弊端——當(dāng)小區(qū)內(nèi)LoRa節(jié)點數(shù)量增多或者同一時刻產(chǎn)生的數(shù)據(jù)包數(shù)量增多時，數(shù)據(jù)包發(fā)生碰撞的概率會大大增加，信息傳輸成功率急劇下降。

在LoRa網(wǎng)絡(luò)中，當(dāng)兩個或多個數(shù)據(jù)包到達(dá)網(wǎng)關(guān)時，同時滿足以下條件，則認(rèn)為發(fā)生沖突：到達(dá)時間上發(fā)生重疊；具有相同的載波頻率；兩個數(shù)據(jù)包使用了相同的擴(kuò)頻因子。此外，當(dāng)兩個數(shù)據(jù)包發(fā)生沖突時，當(dāng)功率較大的LoRa數(shù)據(jù)包比功率較小的LoRa數(shù)據(jù)包大6 dB以上時，會發(fā)生捕獲效應(yīng)[15]：功率較大的數(shù)據(jù)包可以被接收，功率較小的數(shù)據(jù)包丟失。并且一些研究表明，在某些信噪比較低情況下，LoRa的不完美正交性也會影響數(shù)據(jù)包的接收[16]。為了便于建模，本文假設(shè)所有SF都是正交的。

1.3 系統(tǒng)模型

本文對只有一個接收網(wǎng)關(guān)的小區(qū)進(jìn)行建模，其中網(wǎng)關(guān)位于小區(qū)中心，在這個網(wǎng)關(guān)附近存在n個LoRa節(jié)點以隨機(jī)分布的方式分布在網(wǎng)關(guān)周圍半徑為R的區(qū)域中，每個LoRa節(jié)點生成數(shù)據(jù)包的概率服從泊松分布，平均信息生成率為λ，同時忽略該小區(qū)存在的外部干擾，系統(tǒng)場景如圖1所示。

圖1 系統(tǒng)場景

本文使用信息接收率(Data Extraction Rate，DER)作為性能指標(biāo)，其定義為接收到的消息與發(fā)送的消息在一段時間的比率。直接求解最大信息接收率過于困難，故本文將問題轉(zhuǎn)化為如何分配參數(shù)得到最大平均傳輸成功率，其中每個節(jié)點的傳輸成功率為

(10)

通常認(rèn)為使用相同SF的所有節(jié)點都被視為相互干擾，但考慮到捕獲效應(yīng)，可以對模型進(jìn)行如下優(yōu)化：

Cij表示使用相同的SF節(jié)點j是否會和節(jié)點i發(fā)生碰撞：

(11)

(12)

Ni始終小于或等于使用SF的節(jié)點總數(shù)。根據(jù)LoRa接收特性，僅當(dāng)接收信號強(qiáng)度大于接收靈敏度時才可以接收到數(shù)據(jù)包。本文將接收靈敏度作為約束系數(shù)來約束擴(kuò)頻因子和帶寬的選擇，使得節(jié)點可以保證在數(shù)據(jù)可達(dá)網(wǎng)關(guān)的同時分配最佳參數(shù)，從而獲得更好的可靠性：

(13)

表1 接收閾值[17]

帶有約束系數(shù)的節(jié)點平均傳輸成功率及約束條件如下：

(14)

(15)

由公式(1)～(7)可知，較小的SF和較大的BW可以得到較大的傳輸速率，從而縮短傳輸時間；另一方面，較大的SF和較小的BW可以獲得較高的靈敏度，但傳輸速率較低。故本文求解的是一種非線性規(guī)劃問題，接收功率、沖突節(jié)點數(shù)以及傳輸時間三者之間相互制約，最優(yōu)解需要遍歷所有可能的分配方式，復(fù)雜度過高。因此，采用煙花爆炸式混合蛙跳算法尋找次優(yōu)的分配方案來降低復(fù)雜度。

2 煙花爆炸式混合蛙跳算法

文獻(xiàn)[18-19]的研究表明，混合蛙跳算法能夠有效地解決函數(shù)優(yōu)化問題，然而算法在求解過程中也存在易早熟、易陷入局部最優(yōu)等不足。為了解決非線性規(guī)劃問題，本文通過對SFLA進(jìn)行改進(jìn)，提出了一種自適應(yīng)煙花爆炸式混合蛙跳算法。

2.1 混合蛙跳算法

SFLA是對青蛙群體在濕地上跳動覓食行為的一種模擬，通過青蛙個體間的合作與競爭在多維空間中實現(xiàn)對最優(yōu)解的搜索。SFLA首先在可行域內(nèi)生成N只青蛙構(gòu)成初始群體，每一只青蛙都代表一個解，第i只青蛙代表問題的解為Xi=(xi,1,xi,2,…,xi,n)，其中n為解的維數(shù)。求解每只青蛙的目標(biāo)函數(shù)初始值f(Xi)，將每只青蛙的初始值按遞減順序排序，再將青蛙群劃分成m個種群，每個種群含k只青蛙。對每個種群，將目標(biāo)初始值最優(yōu)解記為Xbest，最差解記為Xworst，而在整個青蛙群體中將函數(shù)最優(yōu)解記為Xg。在算法迭代中，只對族群中的Xworst進(jìn)行更新，其策略為

d=rand·(Xbest-Xworst)，

(16)

(17)

當(dāng)每個種群都完成一輪內(nèi)部進(jìn)化后，將各個種群中的個體進(jìn)行混合，并重新排序分組，再進(jìn)行局部搜索。重復(fù)上述操作，直到滿足停止條件。

2.2 自適應(yīng)煙花爆炸式混合蛙跳算法

結(jié)合本文的待優(yōu)化的場景，為了提高算法在離散空間的搜索效率，對基本的混合蛙跳算法引入反向?qū)W習(xí)、煙花爆炸、高斯變異算子和歐氏距離分配種群等操作，提高算法的搜索性能。

2.2.1 反向?qū)W習(xí)初始化

由于SFLA的初始解和最優(yōu)解離得很遠(yuǎn)，所以迭代次數(shù)會很多。而且在局部搜索中，種群中的青蛙個體不能廣泛分布，造成算法的全局搜索能力大大降低。針對這些情況，引入反向?qū)W習(xí)，即加入反向解初始化種群，使青蛙種群具有多樣性。Xi=(xi,1,xi,2,…,xi,n)的反向解定義如下：

(18)

2.2.2 煙花爆炸機(jī)制

SFLA容易出現(xiàn)種群多樣性不足的現(xiàn)象，容易受到局部最優(yōu)解的束縛。為了增加算法進(jìn)化過程中的種群多樣性，本文引入煙花爆炸機(jī)制，其思想源自煙花算法。煙花算法受夜空中煙花爆炸啟發(fā)，通過煙花爆炸產(chǎn)生火花，從而達(dá)到增加種群多樣性的目的。煙花爆炸機(jī)制只在算法陷入瓶頸時再進(jìn)行干預(yù)，即當(dāng)青蛙種群中Xg超過m代沒有更新時，再通過煙花爆炸機(jī)制產(chǎn)生子代青蛙，并將最優(yōu)個體保留至下一代。

在父代青蛙周圍產(chǎn)生子代青蛙數(shù)量如下：

(19)

式中：Si是由Xi產(chǎn)生的子代青蛙數(shù)量；fg是當(dāng)前青蛙種群中適應(yīng)度最大值；ε是為避免除零操作設(shè)置的常數(shù)；Smax為常數(shù)，用來調(diào)整產(chǎn)生子代青蛙的數(shù)目。

產(chǎn)生子代青蛙的搜索半徑如下：

(20)

式中：Ai是由Xi產(chǎn)生子代青蛙的搜索半徑；fb是當(dāng)前青蛙種群中適應(yīng)度最小值；ξ是為避免除零操作設(shè)置的常數(shù)；Amax為常數(shù)，用來調(diào)整搜索半徑。

根據(jù)上述自適應(yīng)煙花爆炸機(jī)制產(chǎn)生的子代個體，與父代青蛙進(jìn)行對比，若優(yōu)于父代，則更新當(dāng)前青蛙，否則不更新。

2.2.3 歐氏距離分配種群

在原始SFLA算法中對青蛙分群按其適應(yīng)度值的高低進(jìn)行分配。結(jié)合本文的編碼規(guī)則，該方法的不足可能會使得相距較遠(yuǎn)的個體分在同一個種群中，從而使迭代的距離較大，使一部分更新后的個體超出編碼范圍(無效解)，影響算法的更新效率，因此本文引入歐氏距離對青蛙劃分種群。新的分配規(guī)則如下：

(1)在群體內(nèi)找到適應(yīng)度值最好的青蛙Xg；

(2)在群體中挑選與青蛙Xg距離最近的p-1只青蛙，將Xg與挑選出的p-1只青蛙組成一個種群；

(3)在種群中除去已挑選過的p只青蛙；

(4)重復(fù)(1)～(3)，直到所有青蛙都分配到屬于自己的種群，每個種群的青蛙數(shù)量為p。

2.2.4 高斯變異算子

SFLA算法迭代過程中的進(jìn)化能力主要依靠最差個體和最優(yōu)個體之間的相互作用，與其他群體智能算法不同的是算法本身不具備變異機(jī)制，這就導(dǎo)致當(dāng)算法陷入局部最優(yōu)解時沒有變異機(jī)制很難走出局部最優(yōu)解的陷阱，算法只在局部最優(yōu)解附近搜索，使整體種群多樣性降低。本文在SFLA更新最差個體時引入高斯變異，新的更新策略如下：

(21)

式中：N(0,1)為標(biāo)準(zhǔn)高斯分布。高斯變異產(chǎn)生的個體會和距離迭代產(chǎn)生的個體進(jìn)行競爭，并保留適應(yīng)度值較好的個體。

2.3 煙花爆炸式混合蛙跳算法主要步驟

2.3.1 個體編碼

假設(shè)種群中有N只青蛙，需要優(yōu)化的場景中共有n個節(jié)點，每一只青蛙都代表一個解，第i只青蛙代表的解為Xi=(xi,1,xi,2,…,xi,n)，xi,j(j∈n)代表節(jié)點j的參數(shù)配置。由式(15)可知,待分配的參數(shù)SF和BW共18種組合，故xi,j∈[0,17],xi,j∈。同時按照傳輸時間Ts升序排列，傳輸時間越長，編碼越大。具體編碼見表2。

表2 編碼表

2.3.2 算法流程

煙花爆炸式混合蛙跳算法主要思想如下：首先，通過反向?qū)W習(xí)生成初始種群；其次，判斷是否達(dá)到煙花爆炸條件；然后，根據(jù)歐氏距離分配種群；最后，引入高斯變異算子，更新最差青蛙的位置。其搜索過程如圖2所示。

圖2 算法流程

3 仿真結(jié)果與性能分析

本文在Python3.6平臺上使用上述煙花爆炸式混合蛙跳算法對目標(biāo)函數(shù)進(jìn)行仿真分析，參數(shù)設(shè)置如表3所示。

表3 算法仿真參數(shù)

為了驗證本文提出的算法有效性和優(yōu)越性，將本文算法與傳統(tǒng)混合蛙跳算法、粒子群算法[12]和遺傳算法[11]進(jìn)行對比。圖3展示了半徑R=1 000 m、節(jié)點個數(shù)為100和500場景下的不同算法適應(yīng)度函數(shù)曲線，可以看出本文提出的算法相較于混合蛙跳算法、粒子群算法和遺傳算法具有更高的收斂精度，相同場景下適應(yīng)度值高2%～5%；同時相較于傳統(tǒng)混合蛙跳算法具有更高的初始值。

(a)節(jié)點個數(shù)為100

(a)節(jié)點個數(shù)為500圖3 適應(yīng)度值與迭代次數(shù)關(guān)系曲線

從圖3還可看出，本文算法相較于另外三種算法不易陷入局部最優(yōu)解。這是因為粒子群算法局部搜索能力較差，粒子移動搜索行為不夠精細(xì)，往往會錯過全局最優(yōu)目標(biāo)值，導(dǎo)致算法早熟收斂，這時粒子的速度幾乎為零，都聚合在一起。雖然此時粒子距離全局最優(yōu)解不遠(yuǎn)，但是幾乎為零的移動速度無法使其跳出局部最優(yōu)解。同樣遺傳算法在面對高維復(fù)雜問題時局部搜索能力較差，單純的遺傳算法比較費(fèi)時，在進(jìn)化后期搜索效率較低，容易產(chǎn)生早熟收斂的問題。而傳統(tǒng)混合蛙跳算法由于進(jìn)化主要靠種群間的相互作用，容易出現(xiàn)早熟、陷入局部最優(yōu)的現(xiàn)象。經(jīng)過改進(jìn)后的算法在尋優(yōu)過程中不斷進(jìn)化直到收斂，當(dāng)算法陷入瓶頸時引入煙花爆炸機(jī)制，在適應(yīng)度值越好的青蛙周圍產(chǎn)生越多的子代青蛙，引導(dǎo)算法向包含全局最優(yōu)的解空間逼近，避免陷入局部優(yōu)化，雖然其收斂速度沒有粒子群算法和遺傳算法快，但是換取了更好的收斂精度。

為了驗證本文算法分配的參數(shù)是否有效，使用基于LoRaSim的仿真平臺進(jìn)行仿真測試。按照算法已分配好的參數(shù)，計算一個小時里小區(qū)內(nèi)LoRa節(jié)點的信息接收率，并與混合蛙跳算法、粒子群算法、遺傳算法和ADR算法分配結(jié)果進(jìn)行對比。如圖4所示，本文算法分配的結(jié)果高于混合蛙跳算法、粒子群算法和遺傳算法5%～10%，相較于ADR提高了40%～50%的信息接收率。

圖4 信息接收率與節(jié)點個數(shù)關(guān)系曲線

本文算法相較于傳統(tǒng)的ADR算法，信息接收率有較大提升，這是因為ADR算法選擇參數(shù)的思路是選擇盡可能小的滿足網(wǎng)關(guān)接受條件的參數(shù)。如圖5所示，當(dāng)單位區(qū)域內(nèi)存在較多節(jié)點時，大部分節(jié)點參數(shù)都集中在SF=7和SF=8，使傳輸過程中碰撞概率大大增加，而本文算法通過優(yōu)化帶有懲罰系數(shù)的平均傳輸成功率函數(shù)，合理分配每種擴(kuò)頻因子數(shù)量，能顯著提高每個節(jié)點的傳輸成功率。

圖5 分配結(jié)果

4 結(jié) 論

為了改善LoRa傳輸過程中的干擾沖突問題，本文提出了一種基于煙花爆炸式混合蛙跳算法的LoRa網(wǎng)絡(luò)參數(shù)分配策略。在SFLA算法的基礎(chǔ)上，加入反向?qū)W習(xí)機(jī)制提升算法的全局搜索能力；加入高斯變異算子提高了算法擺脫局部最優(yōu)解的能力；使用煙花爆炸機(jī)制對個體鄰域進(jìn)行搜索，提高整體種群的多樣性，同時引導(dǎo)算法向全局最優(yōu)解移動，避免陷入局部優(yōu)化。在目標(biāo)優(yōu)化上，以最大化節(jié)點平均傳輸成功率為目標(biāo)，并將接收靈敏度作為約束系數(shù)，使得節(jié)點可以保證在數(shù)據(jù)可達(dá)網(wǎng)關(guān)的同時分配最佳參數(shù)。仿真結(jié)果表明本文提出的算法相較于其他算法具有更好的收斂精度，同時本文算法分配結(jié)果比傳統(tǒng)ADR策略具有更高的信息接收率，能顯著減少傳輸過程中的碰撞概率。實際應(yīng)用中，在高密度節(jié)點場景下，可在滿足LoRa節(jié)點傳輸距離的前提下，通過本文提出的策略分配LoRa網(wǎng)絡(luò)參數(shù)，提高信息傳輸成功率，有效改善傳輸過程中的干擾沖突問題。