王曙光

(西安郵電大學(xué) 自動(dòng)化學(xué)院，陜西 西安 710121)

無線傳感器網(wǎng)絡(luò)的分區(qū)域質(zhì)心定位算法*

王曙光

(西安郵電大學(xué) 自動(dòng)化學(xué)院，陜西 西安 710121)

針對(duì)無線傳感器網(wǎng)絡(luò)(WSNs)質(zhì)心定位算法定位精度較低和一般的改進(jìn)型質(zhì)心算法計(jì)算復(fù)雜及數(shù)據(jù)通信量大的問題，提出一種新的質(zhì)心定位算法——分區(qū)域質(zhì)心定位(RPCL)算法。該算法將包圍未知節(jié)點(diǎn)鄰居錨節(jié)點(diǎn)組成的三角形劃分為7個(gè)區(qū)域，每個(gè)區(qū)域的確定1個(gè)質(zhì)心作為未知節(jié)點(diǎn)的估計(jì)位置。仿真結(jié)果表明：RPCL 算法的平均定位誤差比一般的質(zhì)心定位算法減小20 %以上；參數(shù)優(yōu)化后，誤差減少到49 %左右。

質(zhì)心算法； 定位； 無線傳感器網(wǎng)絡(luò)； 接收信號(hào)強(qiáng)度指示

0 引 言

在無線傳感器網(wǎng)絡(luò)(WSNs)的應(yīng)用中，許多信息與網(wǎng)絡(luò)節(jié)點(diǎn)的位置相關(guān)，節(jié)點(diǎn)定位是一個(gè)重要的研究問題。根據(jù)定位機(jī)制，無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法可分為直接測量法(range-based) 和間接估計(jì)法(range-free)兩類。直接測量法是通過測量節(jié)點(diǎn)間點(diǎn)到點(diǎn)的距離或角度信息，使用三邊測量、三角測量或最大似然估計(jì)定位法計(jì)算節(jié)點(diǎn)位置,常用的方法有接收信號(hào)強(qiáng)度指示( received signal strength indication，RSSI)、到達(dá)角( arrival of angle，AOA)和到達(dá)時(shí)間差( time difference of arrival，TDOA)等[1],這類定位算法精度高，但計(jì)算復(fù)雜，通信數(shù)據(jù)量大，對(duì)節(jié)點(diǎn)的硬件要求也高。間接估計(jì)法只根據(jù)網(wǎng)絡(luò)連通性等信息實(shí)現(xiàn)節(jié)點(diǎn)的定位，算法簡單、成本低、通信開銷小，但定位誤差比較大。

質(zhì)心定位( centroid localization，CL)算法[2]是研究較早的一種典型的間接估計(jì)定位算法,該算法原理簡單，計(jì)算量和通信量較小，容易實(shí)現(xiàn)。但在網(wǎng)絡(luò)節(jié)點(diǎn)非均勻分布時(shí)定位誤差比較大，錨節(jié)點(diǎn)部署的位置對(duì)定位效果影響很大。

本文旨在滿足低開銷(較少通信量)、低成本(較少信標(biāo)，且基本不增加額外硬件)的前提下，提高定位精度[3]，提出了分區(qū)域質(zhì)心定位算法，通過與基本的質(zhì)心算法進(jìn)行比較，顯示了新算法的優(yōu)勢。

1 現(xiàn)有質(zhì)心算法

1.1 質(zhì)心算法原理

質(zhì)心定位算法的原理如圖1所示。

圖1 質(zhì)心定位算法原理圖Fig 1 Principle diagram of centroid localization algorithm

f取值究竟是多少更接近最優(yōu)解，通過仿真實(shí)驗(yàn)來說明。實(shí)驗(yàn)中，為減小偶然誤差，將未知節(jié)點(diǎn)樣本數(shù)量增加到5 000個(gè)，f取值范圍為[1.17,1.25]，每次增加0.01。

(1)

質(zhì)心算法以點(diǎn)代面，把多邊形內(nèi)所有位置都用質(zhì)心位置表示,它的假設(shè)是未知節(jié)點(diǎn)與錨節(jié)點(diǎn)趨于均勻分布，但即便如此，其定位誤差也很大。

1.2 改進(jìn)的質(zhì)心算法

實(shí)際應(yīng)用中，在定位運(yùn)算前，3個(gè)錨節(jié)點(diǎn)互相通信，明確各自的坐標(biāo)，并計(jì)算出7個(gè)區(qū)域的“質(zhì)心”。然后錨節(jié)點(diǎn)調(diào)節(jié)發(fā)射功率，劃分出7個(gè)區(qū)域。未知節(jié)點(diǎn)定位時(shí)，只需要確定和幾個(gè)錨節(jié)點(diǎn)存在通信關(guān)系，即可確定其所在區(qū)域，完成定位。算法的流程如圖3所示。

(2)

式中wi為加權(quán)值。

改進(jìn)的質(zhì)心算法，雖然在不同成都上提高了定位精度，但算法的復(fù)雜性增加，計(jì)算量和通信時(shí)間都有較顯著的增加。而且，如果能夠測得距離錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間的距離，不如用直接測量法定位，這樣精度更高。

2 分區(qū)域質(zhì)心定位算法

2.1 信號(hào)強(qiáng)度與距離的關(guān)系

無線信號(hào)在傳播過程中會(huì)衰減損耗，接收節(jié)點(diǎn)根據(jù)收到的信號(hào)強(qiáng)度，對(duì)比信號(hào)損耗程度，可以得出發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)的距離[8]。無線信號(hào)傳播的路徑損耗常采用對(duì)數(shù)—常態(tài)分布模型

首先觀察圖2中5,6,7這3個(gè)區(qū)域，原來所取的質(zhì)心，太靠近邊緣，與該形狀的中心有一定差距。要減小誤差，應(yīng)對(duì)原質(zhì)心位置作修正。為了計(jì)算簡便，還將質(zhì)心取在原來的中線上。

應(yīng)用型創(chuàng)新人才的培養(yǎng)能否發(fā)揮協(xié)同效應(yīng)，是由系統(tǒng)內(nèi)部各子系統(tǒng)的協(xié)同作用決定的。各學(xué)校的內(nèi)部資源有限，適合特定需求的學(xué)生數(shù)量也有限，如何協(xié)調(diào)各學(xué)校、各專業(yè)、各學(xué)生群體，形成各子系統(tǒng)之間相互協(xié)調(diào)配合，共同圍繞目標(biāo)齊心協(xié)力地運(yùn)作，實(shí)現(xiàn)系統(tǒng)從無序的不穩(wěn)定狀態(tài)向有序的穩(wěn)定狀態(tài)發(fā)展，實(shí)現(xiàn)自我完善和發(fā)展，那么就能產(chǎn)生1+1>2的協(xié)同效應(yīng)。

(3)

式中d為發(fā)射節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的距離，km；PL(d)為經(jīng)過距離d后的路徑損耗，dB；Xδ為均值為0的高斯隨機(jī)變量，其標(biāo)準(zhǔn)差取值范圍為4～10;PL(d0)為d=1 m時(shí)的自由空間信號(hào)損耗；k為路徑衰減因子，取值范圍在2～4之間[9],則節(jié)點(diǎn)的RSSI值為

3.2.1 通信距離系數(shù)的影響

(4)

式中P為發(fā)射功率，G為天線增益。當(dāng)RSSI為0時(shí)，對(duì)應(yīng)的通信距離dmax為極限通信距離。通過控制發(fā)射功率，可以控制最大通信距離dmax

PL(d)=P+G.

(5)

錨節(jié)點(diǎn)的信號(hào)發(fā)射功率是可控的，它的信號(hào)發(fā)射功率經(jīng)過預(yù)先計(jì)算，必須覆蓋質(zhì)心并超出一部分，見圖1所示。設(shè)置一個(gè)通信距離系數(shù)f，用來表示錨節(jié)點(diǎn)最大通信距離與錨節(jié)點(diǎn)到質(zhì)心距離的關(guān)系。

2.2 算法原理

分區(qū)域質(zhì)心定位算法的原理如圖2所示，A,B,C為錨節(jié)點(diǎn)，O為△ABC的質(zhì)心,圖2中的3條弧線分別為3個(gè)錨節(jié)點(diǎn)的信號(hào)覆蓋范圍,這樣，按照不同的信號(hào)覆蓋情況，△ABC被分為7個(gè)部分。

陳主任將呂凌子帶到辦公室的一個(gè)內(nèi)間。內(nèi)間除了辦公桌、文件柜，靠門處還擺放了茶幾和沙發(fā)，看上去比外間至少大了兩倍。

整形：按照“單主干雙主蔓”的樹型整形。主干離架下40 厘米處摘心，培養(yǎng)雙主蔓，主蔓長度為株距一半，主蔓兩側(cè)均勻分布結(jié)果母枝，結(jié)果母枝間距30厘米左右。

圖5的仿真結(jié)果顯示:f取值范圍為1.2～1.22時(shí)，平均誤差接近最小。

圖2 分區(qū)域質(zhì)心定位算法Fig 2 Region partition centroid localization algorithm

對(duì)質(zhì)心算法的改進(jìn)，一般是引入距離關(guān)系，通過測量錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間的距離(或信號(hào)強(qiáng)度)，然后利用極大似然估計(jì)法[4]，或利用權(quán)值函數(shù)對(duì)質(zhì)心修正[5～7]。式(2)為加權(quán)質(zhì)心算法的位置計(jì)算公式

圖3 算法流程圖Fig 3 Flow chart of algorithm

3 算法分析與實(shí)驗(yàn)仿真

3.1 算法的有效性

50 m×50 m的范圍內(nèi)，首先任意確定3個(gè)錨節(jié)點(diǎn)坐標(biāo)。在錨節(jié)點(diǎn)圍成的三角形中，隨機(jī)取一個(gè)點(diǎn)(x，y)作為未知節(jié)點(diǎn)，分別用質(zhì)心算法和分區(qū)域質(zhì)心算法計(jì)算定位誤差。分區(qū)域質(zhì)心算法的通信距離系數(shù)暫取1.2。5次實(shí)驗(yàn)的數(shù)據(jù)如表1所示。

(7)狀態(tài)7(t5～t6)：在t5時(shí)刻，開通Sa4，由于Lr限制了Sa4發(fā)生開通動(dòng)作時(shí)的電流上升速度，所以Sa4在開通時(shí)處于零電流軟開通狀態(tài).從t5時(shí)刻起，Lr與Cr諧振.在t6時(shí)刻，在uCr變化到零，iLr反向變化到最大值IB時(shí)，本狀態(tài)結(jié)束.

表1中，(x，y)為隨機(jī)產(chǎn)生的未知節(jié)點(diǎn)坐標(biāo)，E1為質(zhì)心算法的定位誤差，E2為分區(qū)域質(zhì)心算法的定位誤差。根據(jù)圖1，在區(qū)域1內(nèi)，兩種算法的效果是相同的，如第5次實(shí)驗(yàn)數(shù)據(jù)。在其它區(qū)域內(nèi)，大部分情況下，誤差小于普通的質(zhì)心算法；但也存在一小部分區(qū)域，它離質(zhì)心O的距離比到區(qū)域質(zhì)心的距離還近，如表1中第2次實(shí)驗(yàn)的情況。

“?；~塘”是一種挖深魚塘、墊高基田、塘基植桑、塘內(nèi)養(yǎng)魚的充分利用土地的高效人工生態(tài)系統(tǒng).利用平溪江水源條件推廣“?；~塘”，在促進(jìn)絲蠶生產(chǎn)的同時(shí)發(fā)展養(yǎng)魚業(yè).

表1 5次隨機(jī)實(shí)驗(yàn)數(shù)據(jù)Tab 1 Datas of 5 random test

圖4為隨機(jī)取50個(gè)點(diǎn)，實(shí)驗(yàn)10次的仿真結(jié)果,新的算法誤差平均比原來減小27.3 %。

圖4 仿真結(jié)果Fig 4 Simulation results

3.2 影響誤差的主要因素

預(yù)計(jì)2018年，我國天然氣表觀消費(fèi)量將達(dá)到2710億立方米左右。同時(shí)，保障我國天然氣協(xié)同穩(wěn)定發(fā)展的產(chǎn)供儲(chǔ)銷體系的建設(shè)進(jìn)一步加快。預(yù)計(jì)2020年、2030年、2050年天然氣在我國一次能源消費(fèi)結(jié)構(gòu)中的占比將分別提升至近10%、14%、15%左右。2018年是天然氣產(chǎn)業(yè)深化改革之年，也是天然氣產(chǎn)供儲(chǔ)銷體系建設(shè)的攻堅(jiān)年。必須守住我國天然氣發(fā)展的安全底線，保證天然氣安全平穩(wěn)供應(yīng)，滿足人民日益增長的用氣需求。

RSSI=P+G-PL(d),

本算法把基本質(zhì)心算法的整個(gè)區(qū)域分成了7個(gè)小區(qū)域，區(qū)域1中的點(diǎn)，與使用基本質(zhì)心算法相同,其余6個(gè)區(qū)域中，大部分點(diǎn)的定位誤差會(huì)減小，但在靠近區(qū)域分割線的局部，有可能誤差還會(huì)增大。因此，區(qū)域的劃分對(duì)定位精度有直接影響。而區(qū)域的劃分，是通過錨節(jié)點(diǎn)的通信覆蓋實(shí)現(xiàn)的，也就是上文中提到的通信距離系數(shù)f來決定。最優(yōu)的劃分，應(yīng)該使誤差增大的部分面積最小。

我們一行頂著至少有六級(jí)的大風(fēng)參觀了景區(qū)中的兩個(gè)景點(diǎn)：一是一棵已有數(shù)百年樹齡的參天大樹，樹身掛滿不同色彩的哈達(dá)和風(fēng)馬旗！二是一座放置酥油燈的小屋，酥油燈的火苗在我們眼前不停晃動(dòng)。也許那天正好星期一，景區(qū)除我們一行四人外，未見游人蹤跡。

用數(shù)學(xué)方法計(jì)算這個(gè)面積的表達(dá)式，過于繁瑣。在此做一個(gè)推斷，用實(shí)驗(yàn)法得到一個(gè)近似的最優(yōu)解。

以錨節(jié)點(diǎn)B為例，區(qū)域3的質(zhì)心設(shè)為K,則因?yàn)閨BO|=2|OD|，|OD|=1.5|OK|，所以|OK|=|BO|/3。

讓秦川再找一個(gè)女人的想法是她提出來的。但是她提出來，與秦川真去做了，是兩回事情。她提出來，她不想讓秦川傷心。秦川真做了，秦川將她的心，撕成碎片。

OK的中點(diǎn)作為參考點(diǎn)，它離兩個(gè)質(zhì)心的距離相等,以此點(diǎn)作OD的垂線，可以把各區(qū)域分開。此時(shí)對(duì)應(yīng)的通信距離系數(shù)

f=7/6≈1.167.

但節(jié)點(diǎn)的信號(hào)覆蓋是近似球形的(平面上即圓形)，因此，實(shí)際的f取值應(yīng)該比1.167略大,這也是上述實(shí)驗(yàn)中f取1.2的原因。

圖1中，(x,y)為未知節(jié)點(diǎn)坐標(biāo)；N為相關(guān)錨節(jié)點(diǎn)的數(shù)量；(xi,yi) (i=1,2,…,N)為錨節(jié)點(diǎn)的坐標(biāo)。未知節(jié)點(diǎn)接收到周圍的錨節(jié)點(diǎn)位置信息，把這些錨節(jié)點(diǎn)所組成的多邊形的質(zhì)心作為自己的位置[3]

在這7個(gè)區(qū)域中，各取一個(gè)點(diǎn)，用來表示本區(qū)域中未知節(jié)點(diǎn)的位置。處于區(qū)域1中的未知節(jié)點(diǎn)，其位置仍取△ABC的質(zhì)心O。處于區(qū)域2的未知節(jié)點(diǎn)，其位置取△AOB的質(zhì)心；區(qū)域3,4則分別取△AOC和△BOC的質(zhì)心。區(qū)域5中的未知節(jié)點(diǎn)，其位置取線段AO的中點(diǎn)；區(qū)域6,7同理。

圖5 平均誤差與f的關(guān)系Fig 5 Relationship between average error and f

3.2.2 分區(qū)域質(zhì)心位置的影響

鄧 云(1973-)為本文通訊作者,男,博士,副教授,研究方向:食品加工與營養(yǎng),email:y_deng@sjtu.edu.cn

SIMPLE藥學(xué)服務(wù)模式在支氣管哮喘、COPD患者慢病管理中的實(shí)踐及效果研究 ………………………… 陳 蓉等（10）：1400

本試驗(yàn)以黃芩、黃芪、杜仲、甘草復(fù)合提取物和益生菌（枯草芽孢桿菌）按一定比例制成復(fù)合物，通過研究其對(duì)育肥豬生長性能和胴體性狀的影響，為益生菌與復(fù)方中藥提取物在育肥豬養(yǎng)殖中的推廣應(yīng)用提供理論依據(jù)。

以區(qū)域5為例，將點(diǎn)K1由原來位置向A移動(dòng)，每次移動(dòng)0.02|AO|。5，6,7這3個(gè)區(qū)域的質(zhì)心做同樣的變化，系數(shù)w與平均誤差的關(guān)系如圖6所示。

圖6 平均誤差與w的關(guān)系Fig 6 Relationship between average error and w

系數(shù)w為

w=|OK1|/|OA|.

仿真結(jié)果表明:w取值范圍為0.62～0.64時(shí)，平均誤差接近最小。

(5)2018年6月，在四川工商學(xué)院大創(chuàng)中心路演廳舉辦了2018年云創(chuàng)之聲創(chuàng)新項(xiàng)目孵化大賽，共有52個(gè)項(xiàng)目進(jìn)入初賽行業(yè)，最終角逐出6個(gè)優(yōu)質(zhì)項(xiàng)目；

對(duì)2,3,4這3個(gè)區(qū)域的質(zhì)心，在以上的分析中，它們的都是取的小三角形的質(zhì)心。實(shí)際上，這些小三角形的一部分已經(jīng)成為了區(qū)域1的一部分，這時(shí)的區(qū)域2，3,4，更像是一個(gè)四邊形。以原小三角形的質(zhì)心代替四邊形的質(zhì)心，會(huì)存在一定誤差。

從盈利能力來看，山東產(chǎn)權(quán)交易中心披露的信息顯示，2018上半年，山東高速籃球俱樂部實(shí)現(xiàn)營業(yè)收入3.69億元，凈利潤1.4億元，1-8月份實(shí)現(xiàn)營收3.69億元，凈利潤1.33億元。

用類似的方法，設(shè)系數(shù)p

p=|OK|/|OD|.

由仿真結(jié)果如圖7可見，p取值0.4～0.42范圍時(shí)，平均誤差接近最小。

圖7 平均誤差與p的關(guān)系Fig 7 Relationship between average error and p

綜合上述結(jié)果，取f=1.22，w=0.63，p=0.4，分區(qū)域質(zhì)心算法與原始質(zhì)心算法相比，誤差可減小49 %左右。以上3個(gè)參數(shù)之間還有耦合關(guān)系，本文暫不做討論。

4 結(jié)束語

本文提出的定位算法計(jì)算量小，不增加通信開銷。對(duì)于錨節(jié)點(diǎn)，只需要把發(fā)射電路略作改動(dòng)，由固定功率發(fā)射改為可調(diào)功率發(fā)射，成本增加很少。對(duì)于未知節(jié)點(diǎn)，不需要增加硬件，和讀取接收信號(hào)強(qiáng)度，也不需要根據(jù)信號(hào)強(qiáng)度計(jì)算通信距離，只需要確定和哪個(gè)錨節(jié)點(diǎn)能通信即可，非常簡便。仿真實(shí)驗(yàn)證明了該算法的有效性。

[1] 張愛清,葉新榮,胡海峰.無線傳感器網(wǎng)絡(luò)質(zhì)心定位新算法及性能分析[J].計(jì)算機(jī)應(yīng)用，2012,32(9):2429-2431,2435.

[2] 劉 瑜,衣 曉,何 友.高密度無線傳感器網(wǎng)絡(luò)分簇定位算法[J].系統(tǒng)工程與電子技術(shù)，2012，34(8):1581-1586.

[3] Bulusu N，Heidemann J，Estrin D.GPS-less low-cost outdoor localization for very small devices[J].IEEE Personal Communications Magazine,2000,7(5):28-34.

[4] 張 華，劉玉良，單海校.無線傳感器網(wǎng)絡(luò)改進(jìn)質(zhì)心算法的節(jié)點(diǎn)自定位[J].浙江海洋學(xué)院學(xué)報(bào):自然科學(xué)版,2011,30(4):344-348.

[5] 楊新宇,孔慶茹,戴湘軍.一種改進(jìn)的加權(quán)質(zhì)心定位算法[J].西安交通大學(xué)學(xué)報(bào),2010,44(8):1-4.

[6] 安 恂.一種用于無線傳感器網(wǎng)絡(luò)的質(zhì)心定位算法[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(20):136-138.

[7] 徐小玲，張福強(qiáng)，李少彪.基于APIT的無線傳感器網(wǎng)絡(luò)質(zhì)心算法研究[J].傳感器與微系統(tǒng),2011,30(7):57-60.

[8] 王 勇,胡良梁,袁巢燕.一種環(huán)境自適應(yīng)的無線傳感器網(wǎng)絡(luò)定位算法[J].計(jì)算機(jī)工程,2012,38(6):104-106.

[9] 王新芳,張 冰,馮友兵.基于量子粒子群優(yōu)化的WSNs節(jié)點(diǎn)定位改進(jìn)[J].計(jì)算機(jī)科學(xué),2012,39(6):129-131.

Region partition centroid localization algorithm for WSNs*

WANG Shu-guang

(School of Automation,Xi’an University of Posts & Telecommunications,Xi’an 710121,China)

Aiming at problem of low localization precision of centroid localization algorithm for WSNs,complex calculations and large amount of data communication of general improved centroid algorithm,present a new centroid localization algorithm,region partition centroid localization (RPCL) algorithm.In RPCL,three anchors which near the unknown node enclose a triangle,divides the triangle to seven regions,the centroid of every region as the estimated location of unknown node.Simulation results show that RPCL outperforms centroid localization algorithm by an average less than 20 % in average localization error;the error is reduced to about 49 % after parameter optimizing.

centroid algorithm; localization; wireless sensor networks ( WSNs );

signal strength indication(RSSI)

10.13873/J.1000—9787(2014)12—0149—03

2014—09—03

陜西省自然科學(xué)基金資助項(xiàng)目(2011JM8003);陜西省教育廳科研計(jì)劃資助項(xiàng)目(14JK1679)

TP 393

A

1000—9787(2014)12—0149—03

王曙光(1972-)，男，河北保定人，碩士，副教授，主要研究方向?yàn)榍度胧较到y(tǒng)設(shè)計(jì)、機(jī)器人技術(shù)。