李元熙

（1．無錫商業(yè)職業(yè)技術(shù)學院物聯(lián)網(wǎng)技術(shù)學院 江蘇 無錫：214153；2．江蘇省無線傳感系統(tǒng)應用工程技術(shù)研究開發(fā)中心 江蘇 無錫：214000）

0 引言

隨著智能技術(shù)的興起，自動駕駛作為物聯(lián)網(wǎng)的一種新應用日益成為研究熱點。倉儲區(qū)域內(nèi)自動行駛車輛通常裝載無線模塊和傳感器，其作為一個典型的物聯(lián)網(wǎng)無線節(jié)點與網(wǎng)絡內(nèi)其他節(jié)點按射程以多跳方式組成底層的無線網(wǎng)絡，構(gòu)建出物聯(lián)網(wǎng)的網(wǎng)絡層結(jié)構(gòu)。因此，物聯(lián)網(wǎng)無線節(jié)點的定位問題可以演化為底層無線網(wǎng)絡節(jié)點的定位問題。物聯(lián)網(wǎng)中無線節(jié)點分布離散且不均勻，利用其進行目標定位和跟蹤受環(huán)境、成本等因素影響較大，因而設(shè)計一種底層無線節(jié)點的位置估算方法，在低成本條件下提高定位精度是物聯(lián)網(wǎng)無線節(jié)點在自動駕駛應用中的一個重要需求。

目前，大部分定位算法都是利用一些錨點［1］通過計算連通度或者距離等方式來定位未知節(jié)點，如Shang Y提出的MDS－MAP算法［2］、Niculescu D的DV－Hop或DV－Distance方法［5］等，這些方法雖然成本不高，但由于算法本身受到網(wǎng)絡規(guī)?；蜞従庸?jié)點信息準確度影響，應用場景受限且精度較粗。近些年也有學者提出了新方法，如Tam V利用遺傳算法提出了GAL定位算法和Kannan A．A．提出的SAL算法［5］，這些方法利用群體算法優(yōu)化提高定位精度，但受制于參數(shù)的設(shè)定和計算復雜度，目前都處于發(fā)展階段。

由于無線網(wǎng)絡資源受限，為了在低成本條件下提高物聯(lián)網(wǎng)中底層無線節(jié)點的定位精度，本文混合使用遺傳算法（GA）與模擬退火算法（SA）進行計算，利用退火算法具備概率性向“優(yōu)”和“劣”兩個方向搜索的特點，優(yōu)化遺傳算子，克服“早熟”現(xiàn)象，加速定位值最優(yōu)解計算，提高無線網(wǎng)絡中未知節(jié)點的定位精度和效率。

1 理論與方法

1．1 無線節(jié)點定位方法

無線節(jié)點定位模型采用二維空間表示，每個節(jié)點坐標為（xi，yi）?？臻g共有X個錨點和Y個待測節(jié)點，錨點坐標為（xm，ym）其中m＝1，2，3，…，X，組成錨點坐標向量Xm＝［x1，x2，…，xX］′，Ym＝［y1，y2，…，yX］′。定位問題就可以轉(zhuǎn)換為利用X個錨點，通過通信約束條件求解Y個待測節(jié)點的坐標（xn，yn）其 中Xn＝［xX＋1，xX＋2，…，xX＋Y］′，Yn＝［yX＋1，yX＋2，…，yX＋Y］′，即求解下列的方程：

其 中x，y是 待 測 點 坐 標，x1，2，…，X和y1，2，…，X是錨點坐標，d1，2，…，X是錨點與待測點間的距離。由于實際測量時距離存在誤差，因而定位可以轉(zhuǎn)換成可以求解方程的極小值問題。

在計算距離di時，可采用DV－Hop算法實現(xiàn)估算，該方法使用平均每跳距離Hopzizei替代無線射程作為多跳網(wǎng)絡中每跳的距離，兩點間距離計算公式di＝N×Hopzizei，其中N的待測兩點間的最小跳數(shù)。Hopzizei的計算可利用兩個錨點間距離通過均分跳數(shù)來獲取，計算方法如下

其中hj是當前錨點（xi，yi）與遠程錨點（xj，yj）間的跳數(shù)。DV－Hop方法是利用錨點間多跳距離和來估算直線距離，該方法對硬件要求低，實現(xiàn)簡單，在均勻分布網(wǎng)絡中效果較好，但在非均勻分布或稀疏分布的網(wǎng)絡中，會有誤差。

1．2 遺傳與退火算法

遺傳算法是一種模仿自然生物選擇和進化規(guī)律發(fā)展起來的全局搜索與優(yōu)化方法［2］，在優(yōu)化時采用適度值替代梯度作為選擇依據(jù)，因而具有很強的魯棒性和全局搜素能力。遺傳算法通過選擇、交叉和變異實現(xiàn)父代與子代間的進化。選擇操作利用適度值作為下一代個體出現(xiàn)的概率，體現(xiàn)種群的進化方向；交叉概率Pc是新個體出現(xiàn)的方法，體現(xiàn)了父代與子代間的信息交互；變異概率Pm是給種群帶入小概率擾動以保持種群多樣性，其體現(xiàn)局部搜索能力。

模擬退火算法是將優(yōu)化問題與熱平衡問題進行對比，利用Metropolis準則以一定概率接受“優(yōu)化”與“惡化”解，使算法跳出局部最優(yōu)的陷阱［5］。退火算法過程是從初始溫度開始求解，在等溫過程中由擾動變化出新解后利用Metropolis準則接受新解，冷卻過程利用降溫速率參數(shù)控制迭代過程。退火算法能以最大概率求得最優(yōu)解，具有全局收斂性，對目標和約束函數(shù)沒有要求，具有較廣的適用性。

1．3 優(yōu)化方法

混合算法的優(yōu)化方法是利用遺傳算法全局搜索能力強的優(yōu)勢［4］，結(jié)合退火算法擺脫局部最優(yōu)解，豐富全局并行與局部串行的搜索能力［3］，削弱了算法參數(shù)選擇要求。優(yōu)化方法思路是在遺傳算法的選擇策略中引入退火算法的Metropolis接受準則，即對個體i隨機交換部分基因生成新個體j，i和j通過Metropolis準則競爭進入下一代種群，具體選擇方法如下：計算個體i和j的評價函數(shù)為f（i）和f（j），獲取評價增量Δf＝f（j）－f（i）。當Δf＜0時，新個體j以概率1進入下代種群；當Δf＞0時，隨機在［0，1］間產(chǎn)生一個參考數(shù)r，如果滿足r＜exp（－Δf／T），則仍將新個體j放入下代種群，否則，將原個體i放入下代種群。其Metropolis接受準則如下：

其中P為進入下代種群的接受概率，T為當前溫度。

2 實現(xiàn)過程與參數(shù)設(shè)置

2．1 遺傳算法實現(xiàn)

1）編碼與種群設(shè)定

混合算法中待優(yōu)化的參數(shù)是未知節(jié)點坐標（xn，yn），采用實數(shù)編碼方式有利于降低計算復雜度［6］。在種群數(shù)量設(shè)定方面，一般要求選擇較大的種群規(guī)模有利于多樣性的保持，但過大的種群數(shù)量也將增加計算復雜度，故本文采用經(jīng)驗值設(shè)定為50。

2）適度函數(shù)設(shè)計

遺傳算法的進化方向是通過計算個體的適度值來進行的，本文的混合定位算法選取連通域內(nèi)與待測節(jié)點距離最近的3個錨點作為計算錨點，因此遺傳算法的適度函數(shù)設(shè)計為

其中ki是權(quán)重系數(shù)用于描述距離測量精度，fi（x，y）＝（－di）2，即錨點與待測點位置估值（＾x，＾y）間的差值。

3）選擇算子

選擇算子的設(shè)置既要保證種群多樣性，又要能加速收斂到最優(yōu)解，因而為了防止GA進入局部最佳，選擇算子采用SA算法中的Metropolis接受準則，以一定概率選擇優(yōu)解進入下代種群。

4）交叉算子

為了簡化計算，交叉算子Pc采用單點交叉方式，隨機設(shè)定交叉點。

5）變異算子

變異方式采用優(yōu)先保留優(yōu)勢個體的均勻變異策略，即當個體為最優(yōu)個體時，保留不變，而其他個體用均勻分布的隨機數(shù)選出變異基因。

2．2 模擬退火算法實現(xiàn)

1）加溫操作（初始化設(shè)置）

設(shè)置內(nèi)容包括：設(shè)定初始化溫度T0應該足夠大，令T＝T0，取任意初始解S0，確定每個T時的迭代次數(shù)（即Metropolis鏈長L）。

2）等溫操作（Metropolis抽樣）

對當前解Si增加一個隨機擾動，產(chǎn)生新解Si＋1，計算增量Δf＝f（Si＋1）－f（Si），其中f（Si）是解Si評價函數(shù)。以Metropolis接受準則進行選擇，當Δf＜0時，接受解Si＋1為新的當前解；否則，以概率exp（－Δf／T）接受Si＋1為新解。

3）冷卻操作

該過程對應控制參數(shù)下降，即更新當前溫度為T＝α×T，其中α是［0，1］間的冷卻系數(shù)。

4）終止條件

計算終止條件可以設(shè)置為在連續(xù)若干個Metropolis鏈中都沒有接受新解Si＋1，或者達到設(shè)定結(jié)束溫度時結(jié)束計算，否則降溫后繼續(xù)進行等溫操作。

2．3 算法優(yōu)化

算法流程分為兩大部分，分別是遺傳計算和退火計算，兩者在適度值計算后選擇進入下代種群時產(chǎn)生結(jié)合，利用退火算法優(yōu)化遺傳的選擇過程，具體流程圖如圖1所示。

在該流程中混合算法初始化設(shè)置包含種群規(guī)模M，進化代數(shù)MAXGEN，交叉概率Pc，變異概率Pm，初始溫度T0，冷卻系數(shù)α等。適度函數(shù)選擇帶權(quán)重的距離估算差值，初始化種群時利用DV－Hop算法計算出種群，隨后進入GA算法流程求解每個染色體的適度值，在選擇步驟中引入SA算法，通過擾動產(chǎn)生的新個體使用Metropolis準則接受進入下代種群，同時保持最優(yōu)個體直接進入下代種群，其他個體進入交叉和變異環(huán)節(jié)，這樣在新種群中可以保證每代的最優(yōu)不變，最后進入降溫環(huán)節(jié)，收斂搜索范圍。

圖1 混合遺傳算法流程圖

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

3．1 環(huán)境設(shè)置

文章選擇MATLAB2016作為對定位算法進行測試工具，計算機配置為Intel－i7處理器，8G內(nèi)存，Windows7系統(tǒng)。仿真模擬物聯(lián)網(wǎng)無線節(jié)點部署在100m×100m的區(qū)域內(nèi)（位于第一象限），節(jié)點隨機分布，總數(shù)為100，錨點比例10%，假設(shè)每個節(jié)點具有相同無線射程且布置完成后不再移動。遺傳算法使用Sheffield工具箱，模擬退火算法使用GADST工具箱，算法參數(shù)設(shè)置見表1。

表1 GASA定位算法參數(shù)表

3．2 實驗與分析

為了評價混合遺傳算法的性能，本文將優(yōu)化算法與傳統(tǒng)的遺傳算法做比較，兩種算法選用相同的遺傳參數(shù)，其中交叉概率＝0．8，變異概率＝0．02。從圖2和圖3中可見GASA算法在5代后獲取了最優(yōu)值，而傳統(tǒng)GA算法要在8代后達到最優(yōu)值，因而在函數(shù)尋優(yōu)在收斂速度上GASA要優(yōu)于傳統(tǒng)的GA算法；同時在圖3中最優(yōu)值下降較快，表現(xiàn)出GA算法在早期出現(xiàn)適度值較高的個體后容易陷于早熟收斂，而GASA通過引入退火模擬算法中的Metropolis準則，有利于避免這種情況的發(fā)生，同時對小規(guī)模種群也能通過進化獲取更優(yōu)解。

圖2 GASA算法優(yōu)化過程圖

圖3 傳統(tǒng)GA算法優(yōu)化過程圖

為了評價無線節(jié)點定位的精度，實驗比較了混合遺傳算法與改進DV－Hop算法的定位效果，兩種算法選用相同的10%錨點比例和無線射程，所有節(jié)點在正方形區(qū)域內(nèi)采用均勻隨機分布。圖4給出了10錨點的節(jié)點與90未知節(jié)點分布結(jié)構(gòu)，圖5給出了待定位的90個節(jié)點誤差分布?？梢姴捎没旌线z傳退火算法后未知節(jié)點定位最大誤差為9．3%，最小誤差為0．1%，節(jié)點平均誤差在6．7%。表2列出了5次重復試驗的兩種定位算法的誤差結(jié)果對比，結(jié)果顯示混合遺傳算法比DV－Hop算法在定位精確度上提高了20%左右。

表2 節(jié)點定位誤差表

圖4 100節(jié)點定位分布圖

圖5 GASA算法定位誤差圖

綜上可見，混合遺傳定位算法采用了集群優(yōu)化方法使得無線節(jié)點的定位精度相對較高且波動不大，算法穩(wěn)定；而傳統(tǒng)的定位算法精度不高，每次波動較大，且對節(jié)點分布較為敏感，因而使用混合遺傳定位算法能具有較大優(yōu)勢。

4 結(jié)語

遺傳算法與模擬退火算法是應用較為廣泛的優(yōu)化算法，兩者各具優(yōu)缺。混合兩種算法后可以在種群進化多樣性、早熟現(xiàn)象改進和適度函數(shù)收斂性上獲得較好提升，將其應用于無線節(jié)點的定位后更適用于節(jié)點分布不均，通信約束不強的場合，定位精度、穩(wěn)定性方面也有較大提升，對無基礎(chǔ)設(shè)施的低成本定位系統(tǒng)有很好的指導意義。