移動機器人未知環境下無線基站搜索

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

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

0 引 言

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

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

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

1 無線基站搜索模型與環境模型

1.1 無線信號模型

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

(1)

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

Xα～(0,α2)

(2)

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

(3)

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

Ss=A-10nlog10s

(4)

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

(5)

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

表1 n取值范圍

1.2 機器人環境模型

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

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

圖1 室內環境模型

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

圖2 室外環境模型

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

2.1 天牛須搜索算法原理

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

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

(6)

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

(7)

式中：t為循環次數，xt為t次時天牛的坐標，d0為天牛觸角間的距離。

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

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

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

(8)

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

(9)

(5)結束？

若找到食物(滿足預設條件)或尋找失敗(達到迭代最大值)則結束，反之則繼續步驟(2)～步驟(4)。

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

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

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

x1=x0+step*dir

(10)

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

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

(11)

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

(12)

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

(5)結束？

若找到食物(滿足預設條件)或尋找失敗(達到迭代最大值)則結束，反之則繼續步驟(2)～步驟(4)。

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

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

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

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

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

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

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

(7)預期位置:若找到無線信號源(滿足預設條件)或尋找失敗(達到迭代最大值)則結束，反之則繼續步驟(4)～步驟(7)。

(8)結束。

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

圖3 算法流程

3 實驗仿真與算法分析

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

3.1 室內環境

圖4為室內場景中實驗的結果。設圖4按上到下的順序依次記為圖4(a)、圖4(b)、圖4(c)、圖4(d)。圖4(a) 的初始參數：路徑衰減因子n為2、初始坐標為(22，15)、步長為3(衰減系數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)的其它參數與圖4(a)一致。圖4(a)～圖4(d)表明不同的環境(理想環境、空曠環境、半空曠環境、密閉環境)中不同的路徑衰減速率n(2、2.5、3、3.5)下都可以通過BAS算法成功搜索到無線信號源的位置。

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

3.2 室外環境

圖5為室外場景的實驗結果。設圖5按上到下的順序依次記為圖5(a)、圖5(b)、圖5(c)、圖5(d)。圖5(a) 的初始參數：路徑衰減因子n為2、初始坐標為(7,40)、步長為20(衰減系數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)的其它參數與圖5(a)一致。圖5(a)～圖5(d)表明不同的環境(理想環境、空曠環境、半空曠環境、密閉環境)中不同的路徑衰減速率n(2、2.5、3、3.5)下都可以通過BAS算法成功搜索到無線信號源的位置。

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

3.3.1 實驗結果分析

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

表2 室內場景的統計結果/步數

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

表3 室外場景的統計結果/步數

3.3.2 與經典算法對比分析

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

表4 3種算法對比

3.3.3 算法時間復雜度分析

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

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

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

(13)

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

4 結束語

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