面向車間布局的自適應(yīng)LANDMARC算法*

邵　聰，王　磊，李奇倚，陳云飛

（上海交通大學(xué) 機(jī)械與動(dòng)力工程學(xué)院，上海 200240）

面向車間布局的自適應(yīng)LANDMARC算法*

邵聰，王磊，李奇倚，陳云飛

（上海交通大學(xué) 機(jī)械與動(dòng)力工程學(xué)院，上海 200240）

在車間定位中，運(yùn)用基于有源射頻識(shí)別校驗(yàn)的動(dòng)態(tài)定位（LANDMARC）算法時(shí)，由于車間障礙物引起的多徑效應(yīng)和邊界處參考標(biāo)簽數(shù)量不足，算法無(wú)法正確選擇參考標(biāo)簽中的最近鄰，對(duì)此，提出一種面向車間布局的自適應(yīng)LANDMARC算法。首先引入對(duì)數(shù)距離路徑損耗模型處理RFID讀寫器接收信號(hào)強(qiáng)度指示（RSSI），再通過(guò)對(duì)比法篩選出參考標(biāo)簽有效值以及插值法在邊界插入虛擬標(biāo)簽。對(duì)比傳統(tǒng)LANDMARC算法，將定位平均誤差從0.39 m降低到0.16 m，證明了自適應(yīng)LANDMARC算法的有效性。

LANDMARC；參考標(biāo)簽；最近鄰；自適應(yīng)；對(duì)數(shù)距離路徑損耗模型；RSSI

0　引言

隨著信息技術(shù)與工業(yè)技術(shù)的高度融合，制造業(yè)正面臨新的挑戰(zhàn)，而定制化服務(wù)和柔性生產(chǎn)的引入，使得車間的制造過(guò)程更加復(fù)雜且難以控制，因此對(duì)車間的信息化水平提出了更高要求[1，2]。為了整合車間資源信息，提出了運(yùn)用射頻識(shí)別（Radio Frequency Identification，RFID）技術(shù)[3]實(shí)時(shí)收集車間中人員、物料、生產(chǎn)工具的位置信息來(lái)掌握生產(chǎn)狀態(tài)的方法。RFID是一種可以通過(guò)無(wú)線電信號(hào)識(shí)別特定目標(biāo)的非接觸式無(wú)線通信技術(shù)，RFID定位可以分為基于傳播模型的定位和基于場(chǎng)景分析的定位[4]。

有源射頻識(shí)別校驗(yàn)的動(dòng)態(tài)定位(Location Identification Based on Dynamic Active RFID Calibration，LANDMARC)算法是一種典型的基于場(chǎng)景分析的RFID定位算法，較低成本和較高精度使其成為研究和使用較為廣泛的算法[5]。

1　LANDMARC算法

1.1算法簡(jiǎn)介

LANDMARC算法的核心思想是通過(guò)在定位區(qū)域布置參考標(biāo)簽，選擇參考標(biāo)簽中的最近鄰間接實(shí)現(xiàn)定位。算法中，所有參考標(biāo)簽的坐標(biāo)已知，讀寫器讀取到參考標(biāo)簽以及目標(biāo)標(biāo)簽的接收信號(hào)強(qiáng)度指示(Received Signal Strength Indication，RSSI)值[6]，選取與目標(biāo)標(biāo)簽差異最小的若干參考標(biāo)簽作為最近鄰，然后通過(guò)質(zhì)心算法計(jì)算目標(biāo)標(biāo)簽的坐標(biāo)[7]。

1.2算法求解

假設(shè)在定位區(qū)域布置了M個(gè)讀寫器，N個(gè)參考標(biāo)簽。目標(biāo)標(biāo)簽在M個(gè)讀寫器上的RSSI值用向量表示為：

O=(O1，O2，…，OM)

Ok表示目標(biāo)標(biāo)簽在第 k個(gè)讀寫器上的RSSI值。

同理，所有參考標(biāo)簽在讀寫器上的RSSI值用矩陣表示為：

Rij表示第i個(gè)參考標(biāo)簽在第j個(gè)讀寫器上的RSSI值。

通過(guò)歐幾里得距離公式計(jì)算目標(biāo)標(biāo)簽與參考標(biāo)簽間距離：

Ei表示第 i個(gè)參考標(biāo)簽與目標(biāo)標(biāo)簽的距離。Ei值越小，參考標(biāo)簽與目標(biāo)標(biāo)簽間距離越近。

取k個(gè)Ei值最小的參考標(biāo)簽作為最近鄰計(jì)算權(quán)重：

若k個(gè)取定的最近鄰坐標(biāo)為(xi，yi)，則目標(biāo)標(biāo)簽坐標(biāo)(x，y)為：

1.3算法不足

LANDMARC算法的主要不足有：

(1)計(jì)算量大且易冗余。在選取最近鄰時(shí)，需要對(duì)每個(gè)參考標(biāo)簽進(jìn)行采集并與目標(biāo)標(biāo)簽比對(duì)Ei值，計(jì)算量較大。

(2)前期部署困難。參考標(biāo)簽位置及間隔密度難以衡量，數(shù)量太多導(dǎo)致成本上升且標(biāo)簽間容易產(chǎn)生干擾，數(shù)量太少導(dǎo)致精度下降。

(3)局部精度低。由于車間布局環(huán)境易存在障礙物，會(huì)產(chǎn)生多徑效應(yīng)、反射、衍射等現(xiàn)象，導(dǎo)致局部 RSSI值突變；同時(shí)邊界區(qū)域參考標(biāo)簽不足，也導(dǎo)致局部精度產(chǎn)生一定下降。

2　面向車間布局的自適應(yīng)LANDMARC算法

LANDMARC算法十分依賴最近鄰的選擇，傳統(tǒng)LANDMARC算法選擇最近鄰時(shí)容易出現(xiàn)兩種問(wèn)題導(dǎo)致定位精度下降。

(1)障礙物影響RSSI值。算法容易受環(huán)境中障礙物影響，部分RSSI值突變，錯(cuò)誤地選擇最近鄰。

(2)邊界參考標(biāo)簽數(shù)量不足。由于邊界區(qū)域布置參考標(biāo)簽數(shù)量不足，使得邊界處選擇最近鄰時(shí)可選參考標(biāo)簽數(shù)量過(guò)少。

本文提出自適應(yīng)LANDMARC算法，借鑒基于傳播模型的定位算法引入對(duì)數(shù)距離路徑損耗模型，并通過(guò)對(duì)比法和插值法提升LANDMARC算法選擇最近鄰的準(zhǔn)確度。

2.1對(duì)數(shù)距離路徑損耗模型

對(duì)數(shù)距離路徑損耗模型反映了射頻信號(hào)在室內(nèi)傳播時(shí)信號(hào)強(qiáng)度與傳播距離的關(guān)系[8]：

其中，PL(d)表示讀寫器接收信號(hào)時(shí)RSSI的衰減量，PL(d0)表示在參考點(diǎn)d0處接收信號(hào)時(shí)RSSI的衰減量，單位為 dB；n是路徑損耗系數(shù)，反映射頻信號(hào)衰減速度；Xσ是以dB為單位表示的高斯噪聲。

讀寫器接收到RSSI值為：

通過(guò)變形，并用 a、b替換-10n和Xσ，得：

D為讀寫器與參考標(biāo)簽之間距離；a、b是與讀寫器本身屬性以及環(huán)境有關(guān)的參數(shù)，通過(guò)實(shí)驗(yàn)可測(cè)得。

2.2障礙物誤差解決方案

2.2.1障礙物環(huán)境下誤差來(lái)源

由于車間環(huán)境復(fù)雜，由障礙物引發(fā)的最近鄰選擇錯(cuò)誤情況有：

(1)距離目標(biāo)標(biāo)簽很遠(yuǎn)、毫無(wú)關(guān)系的參考標(biāo)簽，因?yàn)檎系K物影響，Ei值反而更小，被選為最近鄰。

(2)距離目標(biāo)標(biāo)簽很近、最近鄰首選的參考標(biāo)簽，因?yàn)檎系K物影響，Ei值反而更大，退出了最近鄰。

(3)目標(biāo)標(biāo)簽本身處在障礙物環(huán)境中，測(cè)得的 Ok與實(shí)際情況有誤差，導(dǎo)致最近鄰的選擇產(chǎn)生錯(cuò)誤。

LANDMARC算法需要比較目標(biāo)標(biāo)簽與參考標(biāo)簽之間RSSI差值來(lái)確定距離，然后選取Ei相差最小的k個(gè)參考標(biāo)簽作為最近鄰。

以情況(1)為例，如圖1，O為目標(biāo)標(biāo)簽，A、B、C、D應(yīng)該被選擇為最近鄰的參考標(biāo)簽，由于障礙物對(duì)RSSI值干擾，D′替換Ei被判定為最近鄰，最后計(jì)算得到目標(biāo)標(biāo)簽位置為P。

圖1　障礙物環(huán)境下最近鄰選擇示意圖

2.2.2對(duì)比法篩選最近鄰

下面介紹在自適應(yīng)LANDMARC算法中，一種篩選最近鄰的方法。

首先，通過(guò)預(yù)設(shè)實(shí)驗(yàn)測(cè)定當(dāng)前讀寫器和標(biāo)簽在定位環(huán)境中的RSSI-lgD回歸直線(即式(6))。因?yàn)檐囬g布局、讀寫器坐標(biāo)、參考標(biāo)簽的坐標(biāo)已知，可以計(jì)算各參考標(biāo)簽與各讀寫器之間距離，并將距離帶入到回歸直線中，計(jì)算出RSSI值作為標(biāo)準(zhǔn)值。然后，讀寫器開始采集各個(gè)參考標(biāo)簽的RSSI值作為測(cè)量值。最后，將參考標(biāo)簽的RSSI標(biāo)準(zhǔn)值與測(cè)量值進(jìn)行比較，判定是否處于設(shè)定的誤差范圍e，在誤差范圍內(nèi)的RSSI測(cè)量值進(jìn)入?yún)⒖紭?biāo)簽RSSI有效值集合。如果參考標(biāo)簽 RSSI有效值集合中元素個(gè)數(shù)小于最小要求k，則通過(guò)控制參數(shù)λ對(duì)誤差范圍e進(jìn)行控制。

2.3邊界誤差解決方案

2.3.1邊界環(huán)境下誤差來(lái)源

LANDMARC算法在邊界區(qū)域精度往往會(huì)下降。如圖2，O為目標(biāo)標(biāo)簽，A、B、C、D是理想最近鄰，但是實(shí)際上邊界并不存在C、D，導(dǎo)致C′和D′被判定為最近鄰，最后計(jì)算得到目標(biāo)標(biāo)簽位置為P。

圖2　邊界環(huán)境下最近鄰選擇示意圖

2.3.2插值法過(guò)程

假設(shè)讀寫器坐標(biāo)為(xi，yi)，虛擬標(biāo)簽坐標(biāo)為(x0，y0)，距離公式計(jì)算如下：

取lgDm，代入式(6)，即獲得虛擬標(biāo)簽的插值。

2.4自適應(yīng)LANDMARC算法

定義矩陣 Rij標(biāo)：參考標(biāo)簽 RSSI標(biāo)準(zhǔn)值。

定義矩陣 Rij測(cè)：參考標(biāo)簽 RSSI測(cè)量值。

定義矩陣 Rij虛：虛擬標(biāo)簽 RSSI插值值。

定義集合R效：參考標(biāo)簽RSSI有效值集合，所有有效參考標(biāo)簽的集合。

自適應(yīng)LANDMARC算法流程圖如圖3。

圖3　自適應(yīng)LANDMARC算法流程圖

3　實(shí)驗(yàn)驗(yàn)證

3.1車間布局模擬

在4 m×4 m的物流實(shí)驗(yàn)室中，模擬車間布局設(shè)計(jì)了車間生產(chǎn)線并布置障礙物。實(shí)驗(yàn)布局示意圖如圖4。

圖4　實(shí)驗(yàn)布局示意圖

表1　實(shí)驗(yàn)結(jié)果

3.2實(shí)驗(yàn)結(jié)果

分別用傳統(tǒng)LANDMARC算法和自適應(yīng)LANDMARC算法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表1所示。

3.3結(jié)果分析

通過(guò)實(shí)驗(yàn)結(jié)果，得到以下結(jié)論：

(1)傳統(tǒng)LANDMARC算法在局部區(qū)域最近鄰的選擇上明顯錯(cuò)誤，例如5號(hào)標(biāo)簽由于障礙物存在，選擇了較遠(yuǎn)的參考標(biāo)簽，精度明顯下降。

(2)自適應(yīng)LANDMARC算法降低了障礙物對(duì)于算法的影響，例如7號(hào)標(biāo)簽選擇了理想最近鄰。但有時(shí)缺乏穩(wěn)定性，選擇了并不理想的最近鄰，如4號(hào)標(biāo)簽。

(3)自適應(yīng)LANDMARC算法在精度上優(yōu)于傳統(tǒng)LANDMARC算法，平均誤差從0.39 m降低到0.16 m。

4　結(jié)論

本文提出一種面向車間布局的自適應(yīng)LANDMARC算法，通過(guò)對(duì)比法和插值法對(duì)傳統(tǒng)LANDMARC算法進(jìn)行了改進(jìn)。實(shí)驗(yàn)證明了算法的有效性。

本文對(duì)自適應(yīng)LANDMARC算法進(jìn)行的實(shí)驗(yàn)和分析也存在一些不足。例如未進(jìn)行參考標(biāo)簽最優(yōu)布置驗(yàn)證和參考標(biāo)簽密度與定位精度關(guān)系測(cè)量實(shí)驗(yàn)等。

下一步的研究方向?yàn)椋?1)在現(xiàn)有基礎(chǔ)上進(jìn)行參考標(biāo)簽密度與布置實(shí)驗(yàn)，進(jìn)一步尋找提高降低定位誤差的方法；(2)探究初始誤差范圍e和控制參數(shù)λ的設(shè)定對(duì)定位精度的影響；(3)增加實(shí)驗(yàn)布局的復(fù)雜性并添加干擾源，以適應(yīng)實(shí)際的車間情況。

[1]ZHOU W，PIRAMUTHU S.Manufacturing with item-level RFID information：from macro to micro quality control[J].International Journal of Production Economics，2012，135(2)：929-938.

[2]劉愛軍，楊育，邢青松，等.柔性作業(yè)車間多目標(biāo)動(dòng)態(tài)調(diào)度[J].計(jì)算機(jī)集成制造系統(tǒng)，2012，17(12)：2629-2637.

[3]Zhang Min，Li Wenfeng，Wang Zhongyun，et al.A RFID-based material tracking information system[C].Automation and Logistics，2007 IEEE International Conference on.IEEE，2007：2922-2926.

[4]張佳，羅軍勇，王艷，等.改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)定位算法[J].計(jì)算機(jī)工程，2009，35(6)：133-135.

[5]JIN G，LU X，PARK M S.An indoor localization mechanism using active RFID tag[C].Sensor Networks，Ubiquitous，and Trustworthy Computing，2006.IEEE International Conference on.IEEE，2006(1)：4.

[6]段璞，劉春江，武岳山.RSSI在RFID讀寫器中的應(yīng)用[J].計(jì)算機(jī)工程，2010，36(22)：289-290.

[7]LIONEL N I，LIU Y.LANDMARC：indoor location sensing using active RFID[J].Wireless Networks，2004，10(6)：701-710.

[8]崔燕妮，張興輝，楊榮飛，等.基于對(duì)數(shù)距離路徑損耗模型下的路徑損耗指數(shù)研究[C].全國(guó)第十三屆微波集成電路與移動(dòng)通信學(xué)術(shù)會(huì)議論文集，2010：267-271.

Adaptive LANDMARC algorithm for workshop layout

Shao Cong，Wang Lei，Li Qiyi，Chen Yunfei
(School of Mechanical Engineering，Shanghai Jiao Tong University，Shanghai 200240，China)

Due to such complicated layout of workshop as multipath effect led by obstacles and lack of reference tags distributed on the boundaries,location identification based on dynamic active RFID calibration(LANDMARC)algorithm,used in workshop locating, is not capable of selecting the nearest neighbors of the given reference tags effectively.To solve the problem,proposing an original workshop layout-oriented adaptive LANDMARC algorithm.The algorithm firstly introduces logarithmic distance path loss model to process the

signal strength indication(RSSI)from RFID readers,then filters the ones with feasible values out of all reference tags by method of comparison and inserts into the boundary virtual tags obtained by method of interpolation.Compared to traditional LANDMARC,the algorithm reduces the mean error from 0.39m to 0.16m,which clearly shows the effectiveness.

LANDMARC；reference tag；nearest neighbors；adaptive；logarithmic distance path loss model；RSSI

TP212.9；TP274

A

10.16157/j.issn.0258-7998.2015.09.021

國(guó)家自然科學(xué)基金青年項(xiàng)目（61203322）

2015-05-23)

邵聰（1991-），男，碩士研究生，主要研究方向：物聯(lián)網(wǎng)、RFID定位。

王磊（1981-），通信作者，男，博士，助理研究員，主要研究方向：智能制造、數(shù)據(jù)挖掘、生產(chǎn)系統(tǒng)、物聯(lián)網(wǎng)，E-mail：wlei81@sjtu.edu.cn。

李奇倚（1991-），男，碩士研究生，主要研究方向：智能制造、生產(chǎn)調(diào)度。

中文引用格式：邵聰，王磊，李奇倚，等.面向車間布局的自適應(yīng) LANDMARC算法[J].電子技術(shù)應(yīng)用，2015，41(9)：78-81.

英文引用格式：Shao Cong，Wang Lei，Li Qiyi，et al.Adaptive LANDMARC algorithm for workshop layout[J].Application of Electronic Technique，2015，41(9)：78-81.