移動機器人未知環(huán)境下無線基站搜索

廖列法，張幸平+，李 帥，楊翌虢

(1.江西理工大學 信息工程學院，江西 贛州 341000；2.斯旺西大學 工程學院，英國 威爾士 斯旺西 SA1 8EN)

0 引 言

許多生物通過感知氣味信息的變化可以進行自主活動。例如飛蛾利用氣味可以成群飛行[1-3]，魚和鳥利用氣味可以尋找食物[4-6]，蟲類利用氣味可以搜尋營養(yǎng)物質(zhì)[7]。與仿生原理類似，機器人主動嗅覺問題[8,9]可理解為機器人通過感知器的反饋進行自主定位、環(huán)境探索與自主導航等。在一些特定場景下，通過機器人的感知原理能夠完成特定氣味源的定位，比如在火場中可利用機器人搜索火災源以及滅火。因此，特定信號源的定位應用廣泛且具有與人互補的優(yōu)勢。

從函數(shù)優(yōu)化的角度理解定位問題：信號源是信號最強的點，即在全局空間尋找信號最強的位置。信號在傳輸?shù)倪^程中，受到信號輻射與擴散的影響，信號強度從信號源逐漸向外擴散減弱。若可用函數(shù)表示信號強度的變化，則可以通過梯度上升定位信號源。但大多數(shù)情況下，無法確定信號源擴散形成的信號場，不能用函數(shù)進行表示，而且信號受到干擾的影響，可能形成局部最強。近些年，針對在函數(shù)未知的情形下全局尋優(yōu)，往往可以使用蟻群算法[10,11]、粒子群算法[12]、微粒群優(yōu)化(PSO)算法[13,14]、遺傳算法[15,16]、螢火蟲算法[17]等，并且結果大多比較理想。但這些算法往往都源于生物種群思想，即需要很多粒子或者機器人才可以進行搜尋，同時協(xié)作要求高、實時性要求強。

天牛須搜索(beetle antennae search，BAS)算法[18,19]是利用天牛覓食行為的仿生機制提出的一種全局尋優(yōu)方法。它沒有梯度信息，可在函數(shù)未知的情況下，通過單個個體實現(xiàn)高效尋優(yōu)。由此，基于BAS提出一種單機器人尋源算法，并應用于未知環(huán)境下無線基站搜索。

1 無線基站搜索模型與環(huán)境模型

1.1 無線信號模型

無線信號的傳播是從信號源(發(fā)射端)到信號接收(接收端)的過程。在理想狀態(tài)下(沒有干擾和損耗)，其過程符合自由空間傳播模型。但在現(xiàn)實生活中，信號往往會受到各種各樣的影響，比如傳播過程受到建筑物、無線干擾等影響，其過程符合對數(shù)距離損耗模型[20]，公式表達如下

(1)

式中：Ss和Ss0為信號強度(dBm)；s和s0為與發(fā)射端的距離，單位為m，并且s0為參考取值，常為1 m;n為路徑損耗的速率，一般為常數(shù)，取值范圍受到環(huán)境的影響；Xα為正態(tài)隨機變量，α為標準差(3.0 dBm-14.1 dBm)，表示如下

Xα～(0,α2)

(2)

式(1)中Ss受到Ss0(距離為1 m時的信號強度)、n(路徑損耗，比如周圍環(huán)境)、s和s0(距離)、Xα(正態(tài)隨機變量)等影響，對其簡化后的模型可表示為

(3)

另外，設置s0=1,Ss0=A， 式(3)可進一步表示為

Ss=A-10nlog10s

(4)

式中：A為常數(shù)(s0為1時信號的強度)。對式(4)描述了信號強度Ss與距離s的函數(shù)表示，假設信號強度為rssi，s可進一步表示為

(5)

式中：n受到周圍環(huán)境(理想環(huán)境、空曠環(huán)境、半空曠環(huán)境、密閉環(huán)境等)的影響，其參考取值范圍見表1。

表1 n取值范圍

1.2 機器人環(huán)境模型

移動機器人所處的環(huán)境未知，為方便實驗，這里假設分為室內(nèi)和室外兩類，同時將3維空間轉(zhuǎn)換為2維空間。

室內(nèi)場景的2維表示：如圖1所示，為直角坐標系中(20,0)，(20,100)，(80,0)，(80,100)4個頂點組成的區(qū)域，其由房間1、房間2、房間3、房間4、房間5、房間6組成，假設空間中的直線為墻壁，空白區(qū)域為可行走區(qū)域。

圖1 室內(nèi)環(huán)境模型

室外場景的2維表示：如圖2所示，為直角坐標系中(0,0)，(0,200)，(200,0)，(200,200)4個頂點組成的區(qū)域，其包含障礙物1、障礙物2、障礙物3、障礙物4等不規(guī)則不同形狀的障礙物，同理，空白區(qū)域為可行走區(qū)域。

圖2 室外環(huán)境模型

2 基于天牛須搜索的無線信號搜索算法

2.1 天牛須搜索算法原理

BAS算法是源于天牛覓食的仿生機制，其覓食過程主要是通過兩個觸角感知食物氣味強弱的變化，不斷調(diào)整行走的方向，最終找到食物。當左邊方向的氣味更強，則向左邊方向行走，反之則向右側(cè)方向行走。行走的方向是根據(jù)食物氣味的強度動態(tài)調(diào)整，其覓食過程的函數(shù)表達如下：

(1)天牛的起始朝向和兩觸角間的方向都是隨機的，假設為dir，n為空間維數(shù)， rands(n,1) 為隨機方向向量，對其進行歸一化后表示如下

(6)

(2)假設xl和xr為兩觸角的空間坐標，可表示為

(7)

式中：t為循環(huán)次數(shù)，xt為t次時天牛的坐標，d0為天牛觸角間的距離。

(3)假設f(x) 函數(shù)的值為氣味的強度， f(xr) 為左邊方向的氣味函數(shù)， f(xl) 為右邊方向的氣味函數(shù)。

(4)天牛每下一步的位置都是根據(jù)左右兩側(cè)的食物氣味強度來動態(tài)更新，其函數(shù)表示如下

xt=xt-1+δt*dir*sign(f(xl)-f(xr))

(8)

式中：xt-1為上一步天牛的位置，δt為經(jīng)過t次迭代(每次迭代通過一個衰減系數(shù)來更新)后的步長(step)， sign() 為符號函數(shù)。式(8)可簡化為

(9)

(5)結束？

若找到食物(滿足預設條件)或?qū)ふ沂?達到迭代最大值)則結束，反之則繼續(xù)步驟(2)～步驟(4)。

2.2 天牛須無線信號搜索算法原理

從2.1節(jié)天牛須搜索算法原理可知，算法以初始位置、初始方向、步長、步長衰減系數(shù)等作為參數(shù)。首先，以初始參數(shù)計算天牛的下一步運動位置。然后，把初始位置和下一步位置理解為左右兩觸角的位置(位置1和位置2)，兩位置之間的距離為步長。根據(jù)位置1和位置2感知的無線信號強度來動態(tài)調(diào)整運動軌跡，始終朝著信號更強的方向運動。每一次運動后，都把下一步位置和上一步位置更新為位置1和位置2，并通過步長衰減系數(shù)更新步長，如此循環(huán)迭代，直到搜索結束，其具體過程如下：

(1)機器人的參數(shù)：假設x0為起始位置，step為每一步運動的距離，dir為運動的方向。x1為算法計算的下一步位置的坐標。根據(jù)式(9)，x1可表達為

x1=x0+step*dir

(10)

(2)x0和x1為左右兩個方向的坐標， f(x0) 為左邊(x0)方向的函數(shù)， f(x1) 為右邊(x1)方向的函數(shù)。

(3)根據(jù)x0和x1的無線信號強度值，計算下一步的運動位置x2(根據(jù)式(9)的位置更新策略)，表示為

(11)

(4)建立位置迭代模型，其更新策略可表示為

(12)

其中，x0(位置1)表示為位置x0和x1接收到的信號強度更強的位置，x1(位置2)表示為以x0、x1、 f(x0)、 f(x1) 為參數(shù)，根據(jù)BAS算法計算出機器人下一步的運動位置。

(5)結束？

若找到食物(滿足預設條件)或?qū)ふ沂?達到迭代最大值)則結束，反之則繼續(xù)步驟(2)～步驟(4)。

2.3 天牛須無線信號搜索算法流程

(1)初始化:初始化x0(記為位置1)、dir(運動方向)、step(每一步的運動距離)。

(2)計算位置2:把初始參數(shù)x0、dir、step代入式(10)，得出x1， 記為位置2(下一步的運動位置)。

(3)x1更新:如果x1為無效坐標(坐標在障礙物空間內(nèi)或受到障礙物影響需要繞行)，則x1更新為與障礙物的交匯坐標。反之，x1為有效坐標，直接進行下一步。

(4)計算位置x2:把x0、x1、dir、step代入式(11)，得出x2(下一步運動位置)。

(5)x2更新:同理(3)，若x2為無效坐標，則x2更新為與障礙物的交匯坐標。反之，x2為有效坐標，直接進行下一步。

(6)更新位置1和位置2:根據(jù)x1和x2的無線信號強度來動態(tài)調(diào)整運動軌跡，始終朝著信號更強的方向運動。x1和x2的更新策略見式(12)。

(7)預期位置:若找到無線信號源(滿足預設條件)或?qū)ふ沂?達到迭代最大值)則結束，反之則繼續(xù)步驟(4)～步驟(7)。

(8)結束。

圖3為天牛須無線信號搜索算法的流程。

圖3 算法流程

3 實驗仿真與算法分析

實驗分為室內(nèi)場景和室外場景，在仿真工具(MATALAB_R2017b)上進行模擬實驗，記錄天牛須無線信號搜索算法計算的每一次運動位置(坐標)，每一次實驗所有點坐標的連接曲線即為運動軌跡。

3.1 室內(nèi)環(huán)境

圖4為室內(nèi)場景中實驗的結果。設圖4按上到下的順序依次記為圖4(a)、圖4(b)、圖4(c)、圖4(d)。圖4(a) 的初始參數(shù)：路徑衰減因子n為2、初始坐標為(22，15)、步長為3(衰減系數(shù)0.98)、信號源為坐標(70,90) 處的正方形、迭代最大值為100、誤差值為1。圖4(b) 的n為2.5、初始坐標為(48，10)。圖4(c)的n為3，初始坐標為(28，41)。圖4(d)的n為3.5，初始坐標為(26，90)。圖4(b)、圖4(c)和圖4(d)的其它參數(shù)與圖4(a)一致。圖4(a)～圖4(d)表明不同的環(huán)境(理想環(huán)境、空曠環(huán)境、半空曠環(huán)境、密閉環(huán)境)中不同的路徑衰減速率n(2、2.5、3、3.5)下都可以通過BAS算法成功搜索到無線信號源的位置。

圖4 室內(nèi)場景不同起點和相同終點時的實驗結果

3.2 室外環(huán)境

圖5為室外場景的實驗結果。設圖5按上到下的順序依次記為圖5(a)、圖5(b)、圖5(c)、圖5(d)。圖5(a) 的初始參數(shù)：路徑衰減因子n為2、初始坐標為(7,40)、步長為20(衰減系數(shù)0.98)、信號源為坐標(185,185)處的正方形、迭代最大值為100、誤差值為1。圖5(b)的n為2.5、初始坐標為(34,75)。圖5(c)的

圖5 室外場景不同起點和相同終點時的實驗結果

n為3，初始坐標為(10,144)。圖5(d)的n為3.5，初始坐標為(133,30)。圖5(b)、圖5(c)和圖5(d)的其它參數(shù)與圖5(a)一致。圖5(a)～圖5(d)表明不同的環(huán)境(理想環(huán)境、空曠環(huán)境、半空曠環(huán)境、密閉環(huán)境)中不同的路徑衰減速率n(2、2.5、3、3.5)下都可以通過BAS算法成功搜索到無線信號源的位置。

3.3 天牛須無線信號搜索算法分析

3.3.1 實驗結果分析

為保證實驗的有效性和可靠性，室內(nèi)場景中針對路徑衰減因子n的每一次取值(2,2.5,3,3.5)都分別執(zhí)行30、60、120次，記錄下每一次實驗的結果并對實驗數(shù)據(jù)進行統(tǒng)計，統(tǒng)計結果見表2。從表2可知，n的取值對整個實驗的結果影響不大，隨著實驗次數(shù)的增加，機器人移動的坐標數(shù)趨于穩(wěn)定，說明算法在室內(nèi)場景中不同起點的情況下有效。

表2 室內(nèi)場景的統(tǒng)計結果/步數(shù)

同樣，室外場景中也針對n的每一次取值都分別執(zhí)行30、60、120次，記錄下每一次實驗的結果并對實驗數(shù)據(jù)進行統(tǒng)計，統(tǒng)計結果見表3。從表3可知，n的取值對整個實驗的結果影響不大，隨著實驗次數(shù)的增加，機器人移動的坐標數(shù)趨于穩(wěn)定，說明算法在室外場景中不同起點的情況下有效。

表3 室外場景的統(tǒng)計結果/步數(shù)

3.3.2 與經(jīng)典算法對比分析

隨機選取室內(nèi)與室外場景下連續(xù)測試120次，然后對120次的實驗結果取平均，并將其作為搜索無線信號源的位置，再與PSO算法、GA算法進行對比，結果見表4。從表4中可知，BAS與PSO、GA算法對比中可知，BAS的收斂速度最快，驗證了算法的優(yōu)越性。

表4 3種算法對比

3.3.3 算法時間復雜度分析

從2.2節(jié)天牛須無線信號搜索算法原理可知，算法包含動態(tài)計算無線信號與機器人之間的距離和不斷優(yōu)化下一步運動位置兩個部分，故其時間復雜度是這兩部的時間復雜度。假設一次搜索過程中，計算下一步運動位置的次數(shù)(節(jié)點數(shù))為M， 則時間復雜度為o(n2)。

證明[21]：第一部分(算法在優(yōu)化下一步運動位置)：計算f(x) 的最優(yōu)值(信號最強)時，共計算n次，則時間復雜度為o(n)； 第二部分(動態(tài)計算節(jié)點距離)：為了提高算法的準確性與可靠性，每個節(jié)點的取值都是m次后取平均，則時間復雜度為o(n×m)。 算法中m=n， 所以其時間復雜度為

o(n×m+n)≈o(n2)

(13)

動態(tài)計算搜索節(jié)點與無線信號源之間距離的時間復雜度為o(M)， 若M個節(jié)點同時搜索，則時間復雜度為o(M×n2)， 但整個算法中只需要一個機器人完成搜索，即只需要確定單個個體的位置。通過以上的分析可得，算法在單個個體搜索過程中的時間復雜度為o(n2)。

4 結束語

通過天牛須無線信號搜索算法，機器人在未知環(huán)境下進行無線信號源搜尋，只需要一個信號感知器，簡單方便的同時實現(xiàn)了高效的全局尋優(yōu)。實驗結果表明，機器人在仿真的室內(nèi)與室外環(huán)境中都可以完成預定的無線信號源搜尋任務，同時結合與經(jīng)典算法的對方分析，驗證了算法的優(yōu)越性。后續(xù)將在其它此類的應用場景中進一步改善優(yōu)化算法。