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

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

0 引 言

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

LoRaWAN采用星型拓?fù)浣Y(jié)構(gòu)[3]，該星型拓?fù)溆删W(wǎng)關(guān)和多個(gè)LoRa終端節(jié)點(diǎn)互連組成。原則上，每個(gè)節(jié)點(diǎn)都可以選擇網(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(shí)候，各個(gè)終端之間勢(shì)必會(huì)出現(xiàn)干擾問題，大量終端同時(shí)請(qǐng)求發(fā)起通信也會(huì)導(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年提出，算法模擬青蛙群體在濕地上跳動(dòng)覓食的行為，通過青蛙個(gè)體間的合作與競(jìng)爭(zhēng)實(shí)現(xiàn)在多維空間中對(duì)最優(yōu)解的搜索。但混合蛙跳算法與上文提及的遺傳算法、粒子群算法等在進(jìn)行求解時(shí)都存在著傳統(tǒng)群體智能算法通有的易陷入局部最優(yōu)解、收斂精度低等缺陷?；诖耍疚奶岢隽艘环N基于煙花爆炸式混合蛙跳算法的LoRa網(wǎng)絡(luò)資源分配策略。首先，對(duì)混合蛙跳算法引入反向?qū)W習(xí)、自適應(yīng)煙花爆炸、高斯變異算子和歐氏距離分配種群等機(jī)制，提高算法的搜索性能；其次，將帶有約束系數(shù)的平均傳輸成功率作為適應(yīng)度函數(shù)，保證節(jié)點(diǎn)在數(shù)據(jù)可達(dá)網(wǎng)關(guān)的同時(shí)分配最佳參數(shù)，從而獲得更好的可靠性；最后，使用基于LoRaSim的仿真平臺(tái)對(duì)分配好的節(jié)點(diǎn)參數(shù)進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果表明本文算法優(yōu)于其他算法，相較于其他算法具有更好的收斂精度，同時(shí)相較于傳統(tǒng)ADR策略顯著提升了信息接收率，能顯著降低節(jié)點(diǎn)傳輸過程中的碰撞概率。

1 問題描述及模型

1.1 LoRa接收特性

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

(1)

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

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

Rs=BW/2SF，

(2)

Tsym=1/Rs。

(3)

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

Tpreamble=(npreamble+4.25)·Tsym。

(4)

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

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

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

(5)

Tpayload=payload·Tsym。

(6)

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

Ts=Tpayload+Tpreamble。

(7)

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

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

(8)

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

(9)

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

1.2 碰撞分析

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

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

1.3 系統(tǒng)模型

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

圖1 系統(tǒng)場(chǎng)景

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

(10)

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

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

(11)

(12)

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

(13)

表1 接收閾值[17]

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

(14)

(15)

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

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

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

2.1 混合蛙跳算法

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

d=rand·(Xbest-Xworst)，

(16)

(17)

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

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

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

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

由于SFLA的初始解和最優(yōu)解離得很遠(yuǎn)，所以迭代次數(shù)會(huì)很多。而且在局部搜索中，種群中的青蛙個(gè)體不能廣泛分布，造成算法的全局搜索能力大大降低。針對(duì)這些情況，引入反向?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ī)制只在算法陷入瓶頸時(shí)再進(jìn)行干預(yù)，即當(dāng)青蛙種群中Xg超過m代沒有更新時(shí)，再通過煙花爆炸機(jī)制產(chǎn)生子代青蛙，并將最優(yōu)個(gè)體保留至下一代。

在父代青蛙周圍產(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)生的子代個(gè)體，與父代青蛙進(jìn)行對(duì)比，若優(yōu)于父代，則更新當(dāng)前青蛙，否則不更新。

2.2.3 歐氏距離分配種群

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

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

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

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

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

2.2.4 高斯變異算子

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

(21)

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

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

2.3.1 個(gè)體編碼

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

表2 編碼表

2.3.2 算法流程

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

圖2 算法流程

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

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

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

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

(a)節(jié)點(diǎn)個(gè)數(shù)為100

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

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

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

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

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

圖5 分配結(jié)果

4 結(jié) 論

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