引 言

　　節(jié)點(diǎn)的定位是無線傳感網(wǎng)應(yīng)用中的一個(gè)重要問題，位置信息的引入使得WSN的輸出從單一的{數(shù)據(jù)}變?yōu)閧數(shù)據(jù)，位置}形式，使得使用者可以更有效的獲取特定位置和區(qū)域而不是特定傳感器結(jié)點(diǎn)的數(shù)據(jù)，從而為許多新型應(yīng)用如基于位置的路由、跟蹤、建筑物形變測(cè)量等應(yīng)用打開了途徑。

　　無線傳感網(wǎng)節(jié)點(diǎn)定位算法實(shí)現(xiàn)具備兩類輸入：已知錨點(diǎn)及其位置信息，結(jié)點(diǎn)之間的測(cè)量間距。

　　已知定位信息的節(jié)點(diǎn)被稱為錨點(diǎn)。未知節(jié)點(diǎn)與錨點(diǎn)之間的距離，按照實(shí)現(xiàn)方式不同，節(jié)點(diǎn)定位算法分為分布式和集中式兩類，前者的算法是通過分布式的各個(gè)節(jié)點(diǎn)實(shí)現(xiàn)的；后者的算法是通過一個(gè)集中式的節(jié)點(diǎn)來實(shí)現(xiàn)的。本文采用集中式算法。

　　無線傳感網(wǎng)節(jié)點(diǎn)擺放完后就確定了錨點(diǎn)的信息，實(shí)現(xiàn)定位的另外一個(gè)輸入是各個(gè)節(jié)點(diǎn)距離信息。目前采用的測(cè)距方法有：測(cè)量無線電信號(hào)強(qiáng)度（RSSI），測(cè)量無線電信號(hào)覆蓋關(guān)系（Radio Connectivity），測(cè)量普通聲波與無線電到達(dá)時(shí)間差（TDOA），測(cè)量超聲波信號(hào)與無線電到達(dá)時(shí)間差。

　　本文采用RSSI方法來進(jìn)行節(jié)點(diǎn)之間的測(cè)距，實(shí)現(xiàn)簡單，模型成熟，比TDOA等方法容易實(shí)現(xiàn)。

　　利用三角定位的原理，分析了定位與錨節(jié)點(diǎn)數(shù)量的關(guān)系，錨節(jié)點(diǎn)數(shù)量不足時(shí)，利用DV-hop算法計(jì)算多跳距離。錨點(diǎn)信息足夠時(shí)則采用二乘法對(duì)數(shù)據(jù)進(jìn)行處理以獲得平均意義上的節(jié)點(diǎn)位置。

　　無線傳感網(wǎng)中節(jié)點(diǎn)定位與實(shí)際節(jié)點(diǎn)定位信息存在一定誤差，產(chǎn)生誤差的原因有兩個(gè)：無線電信號(hào)傳播模型的不夠準(zhǔn)確，節(jié)點(diǎn)之間存在障礙物，節(jié)點(diǎn)擺放等環(huán)境因素影響。針對(duì)后者，本文提出了一個(gè)方法來預(yù)測(cè)節(jié)點(diǎn)之間是否存在障礙物，來改善節(jié)點(diǎn)定位。

　　用C語言進(jìn)行仿真，驗(yàn)證了考慮障礙物影響后，節(jié)點(diǎn)定位相比于沒有采用障礙物分析時(shí)提高了30％左右。

　　1、 定位原理

　　采用無線信號(hào)刪減模型進(jìn)行測(cè)距，其數(shù)學(xué)表達(dá)式為（1）：

　　式中：precieve為接收無線信號(hào)的強(qiáng)度，psend為無線節(jié)點(diǎn)發(fā)出信號(hào)的強(qiáng)度。

　　在信號(hào)強(qiáng)度刪減模型中，其指數(shù)a設(shè)定為2，忽略干擾，可得矩陣方程：

　　式中：X∈R2，是未知節(jié)點(diǎn)位置，ei∈R2是已知第i個(gè)錨點(diǎn)的位置，Zi是接收信號(hào)的強(qiáng)度，ai為常數(shù)。把式（2）展開可得：

　　給定第i個(gè)錨點(diǎn)信息，X是一個(gè)二次未知數(shù)，這對(duì)解方程有一定難度，把其線性化，第i個(gè)方程減掉第1個(gè)方程可得：

　　給定k個(gè)錨點(diǎn)，可得k-1個(gè)線性方程。

　　通過上面的k-1個(gè)方程組可知，當(dāng)X有3個(gè)變量時(shí)，如X表示三維坐標(biāo)，k=4即k-1=3，可以得到解；k《3時(shí)有多解；k》3時(shí)無解。當(dāng)X有2個(gè)變量，X代表二維坐標(biāo)，k=3有解。

   在無線傳感網(wǎng)節(jié)點(diǎn)定位中，以二維定位為例，若未知節(jié)點(diǎn)知道3個(gè)錨點(diǎn)距離，可定出該節(jié)點(diǎn)位置；若僅知道2個(gè)或更少錨點(diǎn)信息，可利用算法一定程度上定出位置范圍；若錨點(diǎn)距離信息多于3個(gè)，可用優(yōu)化算法來優(yōu)化定位。

　　本文以二維信息為例說明無線傳感網(wǎng)節(jié)點(diǎn)定位問題。

　　2、 節(jié)點(diǎn)定位系統(tǒng)架構(gòu)與障礙物分析

　　無線傳感網(wǎng)節(jié)點(diǎn)定位系統(tǒng)分為分布式和集中式兩種：

　　分布式算法將計(jì)算工作分布到各個(gè)節(jié)點(diǎn)中，節(jié)點(diǎn)的位置估計(jì)在本地完成。在非多跳方式中，算法使用的距離參數(shù)在節(jié)點(diǎn)一跳范圍內(nèi)取得；在多跳方式中，這個(gè)參數(shù)由節(jié)點(diǎn)間協(xié)作、多跳取得。

　　在集中式中，中心計(jì)算機(jī)負(fù)責(zé)計(jì)算每個(gè)節(jié)點(diǎn)位置，每個(gè)節(jié)點(diǎn)把自己的信息都統(tǒng)一發(fā)到某一中心節(jié)點(diǎn)，由這個(gè)中心節(jié)點(diǎn)傳到一計(jì)算機(jī)集中處理數(shù)據(jù)并給這些未知節(jié)點(diǎn)定位。見圖1。

　　集中式方法實(shí)現(xiàn)容易，考慮全局信息后能優(yōu)化節(jié)點(diǎn)定位。本文采用集中式定位算法。

　　預(yù)測(cè)障礙物的算法解決方案提高節(jié)點(diǎn)定位的

　　2.1 集中式定位算法實(shí)現(xiàn)

　　采用集中式算法后，多跳范圍的節(jié)點(diǎn)與節(jié)點(diǎn)距離采用DV-hop算法，即平均每跳距離×跳數(shù)的方式。其實(shí)現(xiàn)過程如下。

　　2.1.1 平均每跳距離及錨點(diǎn)到未知節(jié)點(diǎn)跳數(shù)計(jì)算

　　分為2個(gè)階段，即2次廣播過程。

　　個(gè)階段，每個(gè)信標(biāo)節(jié)點(diǎn)采用廣播方式將其位置信息傳遞給其它的信標(biāo)節(jié)點(diǎn)。廣播的信息包格式為：{IDi，xi，yi，Hopsi}，其中包含了該節(jié)點(diǎn)的標(biāo)識(shí)位置坐標(biāo)IDi以及跳數(shù)Hopsi信息。初始Hopsi為1，接收到此數(shù)據(jù)的每個(gè)節(jié)點(diǎn)，將此信息記錄到一張表中。然后繼續(xù)向新的鄰居節(jié)點(diǎn)廣播，每廣播就將Hopsi加1。當(dāng)節(jié)點(diǎn)接收到一個(gè)相同ID的數(shù)據(jù)包時(shí)，便要與原來的Hopsi進(jìn)行比較，如果新的跳數(shù)小于原表中的跳數(shù)，就用新的跳數(shù)更新表中的跳數(shù)信息，意味著找到了一條更短的到達(dá)該信標(biāo)節(jié)點(diǎn)的路徑。如果新的跳數(shù)大于原表中的跳數(shù)，就丟棄該數(shù)據(jù)包，也不再進(jìn)行轉(zhuǎn)發(fā)。

　　經(jīng)過階段的廣播過程后，信標(biāo)節(jié)點(diǎn)也獲得其它所有信標(biāo)節(jié)點(diǎn)的坐標(biāo)及跳數(shù)距離，而且所有傳感器節(jié)點(diǎn)都已經(jīng)得到所有信標(biāo)節(jié)點(diǎn)的坐標(biāo)和跳數(shù)距離。這樣，每個(gè)信標(biāo)節(jié)點(diǎn)即可用式（8）計(jì)算出信標(biāo)節(jié)點(diǎn)i到其他信標(biāo)節(jié)點(diǎn)j的每跳平均間隔距離：

　　其中j是除i之外的所有其它信標(biāo)節(jié)點(diǎn)。

　　第二個(gè)階段，每個(gè)信標(biāo)節(jié)點(diǎn)將每跳平均距離傳送至中心計(jì)算機(jī)，數(shù)據(jù)包的格式為：{IDi，Ci}，Ci是該信標(biāo)節(jié)點(diǎn)到所有其它信標(biāo)節(jié)點(diǎn)的每跳平均距離。中心計(jì)算機(jī)就將所有信標(biāo)節(jié)點(diǎn)平均每跳距離相加取平均：

　　式中：n為所有信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)。由此得到了全網(wǎng)所有信標(biāo)節(jié)點(diǎn)之間的每跳平均距離。各個(gè)節(jié)點(diǎn)也得到各個(gè)信標(biāo)節(jié)點(diǎn)的跳數(shù)。由此可計(jì)算出該節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離：Di=hops×cc。在圖2的示例中，節(jié)點(diǎn)0和5之間的距離，等于跳數(shù)5乘以cc。

　　2.1.2 節(jié)點(diǎn)定位

　　所有未知節(jié)點(diǎn)到錨點(diǎn)的距離算出后即可定位，分為3種情況：

　?。?） 未知節(jié)點(diǎn)與3個(gè)錨點(diǎn)距離已算出；

　　直接采用式（6），式（7）三角定位原理算出該節(jié)點(diǎn)位置。

　　（2） 未知節(jié)點(diǎn)與小于3個(gè)錨點(diǎn)距離已算出；

　　若有2個(gè)錨點(diǎn)距離算出，取該兩點(diǎn)線段中心作為該未知節(jié)點(diǎn)位置；若只有一個(gè)錨點(diǎn)距離算出，則以該錨點(diǎn)位置作為未知節(jié)點(diǎn)位置；若無錨點(diǎn)距離算出，以隨機(jī)經(jīng)驗(yàn)值分配該節(jié)點(diǎn)位置。

　　（3） 未知節(jié)點(diǎn)與大于3個(gè)錨點(diǎn)距離已算出；

　　利用二乘取這組錨點(diǎn)信息來估算未知節(jié)點(diǎn)位置，把式（5）化為式（10）：

　　2.2 誤差及障礙物分析

　　2.2.1 障礙物引起的誤差及障礙物預(yù)測(cè)方法

　　無線傳感網(wǎng)節(jié)點(diǎn)估算定位與實(shí)際節(jié)點(diǎn)位置之間存在誤差，產(chǎn)生誤差的原因有2個(gè)：（1）Rssi方法進(jìn)行測(cè)距時(shí)，無線信號(hào)刪減模型隨環(huán)境變化有所不同，這種模型不能很好的適應(yīng)實(shí)際情況，在對(duì)節(jié)點(diǎn)定位時(shí)會(huì)產(chǎn)生誤差；（2）實(shí)際環(huán)境中，節(jié)點(diǎn)與節(jié)點(diǎn)之間可能存在障礙物，導(dǎo)致此兩節(jié)點(diǎn)運(yùn)用RSSI測(cè)距得出的信號(hào)強(qiáng)度大大小于無障礙物時(shí)的情況。

　　本文采用RSSI方法來進(jìn)行節(jié)點(diǎn)之間的測(cè)距，節(jié)點(diǎn)間若存在障礙物，則測(cè)出的信號(hào)強(qiáng)度與實(shí)際節(jié)點(diǎn)之間的距離有很大偏差。

　　用算法預(yù)測(cè)障礙物的存在位置，把障礙物的影響考慮到節(jié)點(diǎn)定位中有助于節(jié)點(diǎn)定位。

　　本文提出一種預(yù)測(cè)障礙物的三角預(yù)測(cè)法，改 進(jìn)由于節(jié)點(diǎn)之間存在障礙物引起的定位誤差（見圖3）。

　　在a，b，c 3個(gè)節(jié)點(diǎn)之間預(yù)測(cè)其中間有無障礙物，測(cè)得信號(hào)強(qiáng)度：

　　RSSab（a接收到b信號(hào)的強(qiáng)度），RSSac（a接收到c信號(hào)的強(qiáng)度），RSSbc（b接收到c信號(hào)的強(qiáng)度）。

　　l1=f（RSSab），a到b的距離；l2=f（RSSac），a到c的距離；l3=f（RSSbc），b到c的距離。

　　這樣可以估算出ab，ac，bc的長度l1，l2，l3。

　　a，b，c都為一跳鄰居節(jié)點(diǎn)，相互靠的比較近，滿足三角形兩邊邊長之和大于第三邊的定理。這里通過計(jì)算發(fā)現(xiàn)l1》l2+l3，即兩邊之和小于第三邊。則可預(yù)測(cè)a和b之間可能存在障礙物。

　　定位算法是一個(gè)需要迭代比較復(fù)雜的過程，運(yùn)用障礙物分析會(huì)使定位算法程序變得很復(fù)雜，一種好的解決方法是取少量可能存在障礙物的鄰居節(jié)點(diǎn)進(jìn)行障礙物分析，大多數(shù)都無需分析，這樣的節(jié)點(diǎn)對(duì)有以下特征：信號(hào)強(qiáng)度低于某一域值。

　　障礙物導(dǎo)致無線信號(hào)信息不可得，這種情況看作錨點(diǎn)與未知節(jié)點(diǎn)距離太遠(yuǎn)無法通信，本文考慮引入障礙物后無線信號(hào)強(qiáng)度減弱，仍可得到無線信號(hào)。

　　2.2.2 障礙物分析算法實(shí)現(xiàn)

　　本文的定位基本算法如3.1所述，在3.1的算法中，取得了未知節(jié)點(diǎn)到錨點(diǎn)的距離和計(jì)算未知之間插入障礙物分析，見圖3。

　　步，在取得i點(diǎn)與錨點(diǎn)j距離后，做循環(huán)搜索是否有m點(diǎn)同時(shí)與i和j點(diǎn)有距離信息，若有則進(jìn)入障礙物分析，否則退出。

　　第二步，根據(jù)i，j，m三點(diǎn)距離信息，利用3.2.1所述的障礙物分析算法判斷i和j之間是否有障礙物。

　　第三步，如有障礙物，則根據(jù)i節(jié)點(diǎn)信息作如下處理：（1）若i有3個(gè)以上錨點(diǎn)距離信息，則直接丟棄該j錨點(diǎn)的距離信息；（2）若i僅有3個(gè)及以下（包括該j節(jié)點(diǎn)）錨點(diǎn)距離信息，則i和j的距離取一個(gè)經(jīng)驗(yàn)值代替由于障礙物所得的距離值。

　　3 、仿真結(jié)果

　　采用C語言仿真，按照前面的算法進(jìn)行仿真。論證引入障礙物分析后定位的提高，仿真在50 m×50 m的區(qū)域內(nèi)進(jìn)行，錨節(jié)點(diǎn)為4～16個(gè)不等，節(jié)點(diǎn)通信距離為10 m，放置忽略厚度的障礙板8塊，每塊長5 m。比較在有障礙物的情況下一般算法和引入障礙物分析算法后定位的（見圖4）。

　　4、 結(jié) 論

　　本文分析了定位算法理論，提出了定位算法需要解決的幾個(gè)關(guān)鍵問題，提出了一個(gè)新的預(yù)測(cè)障礙物的算法，提高了節(jié)點(diǎn)定位的。采用C語言，通過仿真結(jié)果來論證引進(jìn)障礙物分析后定位的提高。