毛玉明

應(yīng)用三維彈簧系統(tǒng)模型的錨節(jié)點(diǎn)部署優(yōu)化*

毛玉明**

（山東交通學(xué)院信息科學(xué)與電氣工程學(xué)院，濟(jì)南 264200）

為使隨機(jī)部署的三維無(wú)線傳感器網(wǎng)絡(luò)中錨節(jié)點(diǎn)的分布更加合理，提高未知節(jié)點(diǎn)定位精度，針對(duì)錨節(jié)點(diǎn)部署進(jìn)行優(yōu)化。通過構(gòu)建彈簧系統(tǒng)模型，將錨節(jié)點(diǎn)抽象為通過彈簧相連接的點(diǎn)，使部分錨節(jié)點(diǎn)在合力作用下進(jìn)行伸縮運(yùn)動(dòng)，達(dá)到提高網(wǎng)絡(luò)性能的目的。當(dāng)錨節(jié)點(diǎn)部署優(yōu)化完成后，應(yīng)用近似三角形內(nèi)點(diǎn)測(cè)試（APIT）和DV-HOP（Distance Vector-hop）算法測(cè)試優(yōu)化前后的節(jié)點(diǎn)定位精度。仿真結(jié)果表明，三維空間下的錨節(jié)點(diǎn)經(jīng)過彈簧系統(tǒng)模型的部署優(yōu)化后，錨節(jié)點(diǎn)網(wǎng)絡(luò)覆蓋率和定位覆蓋率均得到了提高，網(wǎng)絡(luò)平均連通度有所提升，且定位精度顯著提高。

無(wú)線傳感器網(wǎng)絡(luò)；彈簧系統(tǒng)模型；錨節(jié)點(diǎn)；部署優(yōu)化

現(xiàn)有的無(wú)線傳感器網(wǎng)絡(luò)錨節(jié)點(diǎn)部署方式中大部分為自由部署，通過在監(jiān)測(cè)區(qū)域隨機(jī)拋撒來(lái)實(shí)現(xiàn)，隨機(jī)拋撒的不確定性難以滿足設(shè)計(jì)要求，為達(dá)到較高的定位精度和區(qū)域覆蓋率，需要的錨節(jié)點(diǎn)數(shù)目較多且容易出現(xiàn)覆蓋空洞、錨節(jié)點(diǎn)冗余和信道干涉等現(xiàn)象［3］；其次為確定性部署，通過制定部署方案，采用人工安置錨節(jié)點(diǎn)，這種方式雖然使整個(gè)網(wǎng)絡(luò)成本最低，但在大規(guī)模節(jié)點(diǎn)部署中并不適用，適用范圍有限［4］；最后為移動(dòng)錨節(jié)點(diǎn)隨機(jī)部署并優(yōu)化，錨節(jié)點(diǎn)隨機(jī)部署完成后，通過移動(dòng)錨節(jié)點(diǎn)來(lái)小幅度地調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)，降低了網(wǎng)絡(luò)成本，提高了網(wǎng)絡(luò)覆蓋率和定位精度，但是由于移動(dòng)錨節(jié)點(diǎn)的能量限制，錨節(jié)點(diǎn)的移動(dòng)范圍受限，因此需要通過部署優(yōu)化算法來(lái)限定錨節(jié)點(diǎn)的移動(dòng)路線［5-6］。

本文針對(duì)應(yīng)用廣泛的三維無(wú)線傳感器網(wǎng)絡(luò)，研究移動(dòng)錨節(jié)點(diǎn)的部署優(yōu)化機(jī)制，設(shè)計(jì)了一種三維彈簧系統(tǒng)模型針對(duì)隨機(jī)部署的錨節(jié)點(diǎn)進(jìn)行優(yōu)化，使錨節(jié)點(diǎn)分布更加均勻，增加了網(wǎng)絡(luò)覆蓋率、錨節(jié)點(diǎn)定位覆蓋率和網(wǎng)絡(luò)的連通性。已有部分學(xué)者將彈簧系統(tǒng)模型應(yīng)用于靜態(tài)節(jié)點(diǎn)的定位中：朱慧勇［7］利用彈簧模型計(jì)算DV-HOP（Distance Vector-hop）算法中的平均跳距，相應(yīng)提高了靜態(tài)節(jié)點(diǎn)定位精度；陳萬(wàn)明［8］將節(jié)點(diǎn)虛擬為具有質(zhì)量的粒子，粒子間互相使用彈簧相連，定位算法模擬外力將未知節(jié)點(diǎn)隨機(jī)拉伸至某一位置，粒子在彈簧力作用下回到的位置即是定位位置。以上兩種算法僅是通過模擬彈簧的伸縮運(yùn)動(dòng)來(lái)對(duì)未知節(jié)點(diǎn)定位，節(jié)點(diǎn)實(shí)際并未移動(dòng)且所有節(jié)點(diǎn)均需參與運(yùn)算，造成整體能耗過高。本文算法將彈簧系統(tǒng)模型應(yīng)用于可移動(dòng)錨節(jié)點(diǎn)的部署中，錨節(jié)點(diǎn)在彈簧力的作用下是真實(shí)運(yùn)動(dòng)的，且本文算法針對(duì)的是大規(guī)模隨機(jī)部署的三維網(wǎng)絡(luò)，僅移動(dòng)部分錨節(jié)點(diǎn)，并應(yīng)用現(xiàn)有定位算法即可取得較好的效果。

2　彈簧系統(tǒng)模型

首先做如下假設(shè)：

假設(shè)1 三維無(wú)線傳感器網(wǎng)絡(luò)中只有錨節(jié)點(diǎn)可以移動(dòng)，未知節(jié)點(diǎn)并不移動(dòng)，且錨節(jié)點(diǎn)的能量是有限的，隨著能量耗盡，錨節(jié)點(diǎn)死亡。

假設(shè)2 錨節(jié)點(diǎn)與未知節(jié)點(diǎn)具有相同的通信半徑r。

假設(shè)3 錨節(jié)點(diǎn)可在彈簧模型系統(tǒng)中抽象為一個(gè)點(diǎn)；而對(duì)于未知節(jié)點(diǎn)，為避免錨節(jié)點(diǎn)運(yùn)動(dòng)過程中與未知節(jié)點(diǎn)發(fā)生碰撞，將未知節(jié)點(diǎn)抽象為實(shí)心球形障礙物。

假設(shè)4 在通信半徑r內(nèi)的所有節(jié)點(diǎn)均可以直接相互通信，節(jié)點(diǎn)可以通過它們的ID來(lái)區(qū)分它們。

下面給出適用于三維無(wú)線傳感器網(wǎng)絡(luò)錨節(jié)點(diǎn)部署優(yōu)化的彈簧系統(tǒng)模型。圖1給出了彈簧系統(tǒng)模型N=（P，S）的原理示意圖，其中P為錨節(jié)點(diǎn)集合，S為彈簧集合。圖1中節(jié)點(diǎn)Pi∈P表示三維無(wú)線傳感器網(wǎng)絡(luò)中的一個(gè)可移動(dòng)錨節(jié)點(diǎn)，彈簧Sij∈S連接網(wǎng)絡(luò)中錨節(jié)點(diǎn)Pi和Pj，每一根彈簧都具有3個(gè)屬性：彈性系數(shù)c、彈簧的初始長(zhǎng)度l0和當(dāng)前長(zhǎng)度lij，錨節(jié)點(diǎn)Pi只與其三跳范圍內(nèi)的其余錨節(jié)點(diǎn)之間存在彈簧力。

圖1　彈簧模型原理示意圖Fig.1　The theory of spring model

彈簧Sij的當(dāng)前長(zhǎng)度為錨節(jié)點(diǎn)Pi和Pj的歐氏距離。彈簧的彈力公式如下：

式中：Fi，j為彈簧Sij變形所產(chǎn)生的彈力；cij為彈性系數(shù)；lij為彈簧Sij的當(dāng)前長(zhǎng)度；l0為彈簧Sij的初始長(zhǎng)度。

假設(shè)錨節(jié)點(diǎn)Pi、Pj的坐標(biāo)分別是（xi，yi，zi）和（xj，yj，zj），則彈簧Sij的當(dāng)前長(zhǎng)度lij為

假設(shè)模型中存在3種初始長(zhǎng)度的彈簧，即l1、l2和l3，其彈性系數(shù)c相同，但初始長(zhǎng)度不同，其中：

對(duì)于錨節(jié)點(diǎn)Pi，其所受的合力為

根據(jù)以上公式，可將三維傳感器網(wǎng)絡(luò)中的錨節(jié)點(diǎn)關(guān)系抽象如下：

（1）任一個(gè)錨節(jié)點(diǎn)Pi與其三跳范圍內(nèi)的其他錨節(jié)點(diǎn)間存在虛擬的彈簧力，該力既可能是引力，也可能是斥力，也有可能恰好為0，如圖2所示；

（2）錨節(jié)點(diǎn)間通過互相通信，可獲得相互間的歐氏距離，即彈簧Sij的當(dāng)前長(zhǎng)度lij，并根據(jù)選擇系數(shù)λ設(shè)定彈簧Sij的初始長(zhǎng)度；

（3）錨節(jié)點(diǎn)Pi所受合力為相鄰三跳范圍內(nèi)的錨節(jié)點(diǎn)對(duì)其施加的引力和斥力的矢量和，如圖2所示；

（4）錨節(jié)點(diǎn)Pi在受到合力的作用下做直線運(yùn)動(dòng)，經(jīng)過移動(dòng)后，若所受合力為0或小于閾值?時(shí)，則停止移動(dòng)；

（5）錨節(jié)點(diǎn)在運(yùn)動(dòng)過程中，根據(jù)其安裝的旋轉(zhuǎn)定向天線來(lái)判別運(yùn)動(dòng)路線中的未知節(jié)點(diǎn)，能自動(dòng)繞過未知節(jié)點(diǎn)避免發(fā)生碰撞。

圖2　錨節(jié)點(diǎn)受力示意圖Fig.2　Force diagram of anchor nodes

3　基于彈簧系統(tǒng)模型的錨節(jié)點(diǎn)部署優(yōu)化算法

在錨節(jié)點(diǎn)部署優(yōu)化時(shí)，應(yīng)盡量將在未知節(jié)點(diǎn)密度大的區(qū)域多布置錨節(jié)點(diǎn)，在未知節(jié)點(diǎn)密度小的區(qū)域少布置錨節(jié)點(diǎn)，這樣可以減小定位誤差，提高定位精度。因此錨節(jié)點(diǎn)首先通過與周圍未知節(jié)點(diǎn)的通信來(lái)感知自身三跳范圍內(nèi)未知節(jié)點(diǎn)的數(shù)量，數(shù)量越多則證明錨節(jié)點(diǎn)周圍未知節(jié)點(diǎn)密度越高，應(yīng)使其余錨節(jié)點(diǎn)更靠近該區(qū)域。

根據(jù)錨節(jié)點(diǎn)三跳范圍內(nèi)未知節(jié)點(diǎn)的數(shù)量，選取前10%的錨節(jié)點(diǎn)做固定部署，這樣既可使錨節(jié)點(diǎn)趨向于節(jié)點(diǎn)密度高的區(qū)域，又加快了錨節(jié)點(diǎn)部署優(yōu)化的速度，是一種分布式的部署策略；其次錨節(jié)點(diǎn)在做若干次優(yōu)化部署后，有可能能量即將耗盡，因此可設(shè)置能耗閾值，當(dāng)節(jié)點(diǎn)能量小于時(shí)，也將此錨節(jié)點(diǎn)作固定部署，在彈簧系統(tǒng)模型中可假設(shè)做固定部署的錨節(jié)點(diǎn)被圖釘固定到空間中，其余錨節(jié)點(diǎn)在彈簧力的作用下進(jìn)行收縮擴(kuò)展運(yùn)動(dòng)，如圖3所示。

圖3　錨節(jié)點(diǎn)部署優(yōu)化示意圖Fig.3　Optimal deployment of anchor nodes

基于彈簧系統(tǒng)模型的錨節(jié)點(diǎn)三維部署優(yōu)化算法如下：

（1）錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間相互通信，計(jì)算錨節(jié)點(diǎn)三跳范圍內(nèi)的未知節(jié)點(diǎn)數(shù)量；

（2）錨節(jié)點(diǎn)洪泛自身的信息，信息包括錨節(jié)點(diǎn)ID、三維坐標(biāo)、剩余能量和周圍未知節(jié)點(diǎn)數(shù)量；

（3）錨節(jié)點(diǎn)經(jīng)過相互通信選取固定錨節(jié)點(diǎn)，并計(jì)算自身所受合力，獲得將要到達(dá)的新坐標(biāo)；

（4）錨節(jié)點(diǎn)按照直線進(jìn)行移動(dòng)，通過旋轉(zhuǎn)天線規(guī)避路線上的未知節(jié)點(diǎn)；

（5）所有錨節(jié)點(diǎn)所受合力為0或小于某一極小值時(shí)，部署結(jié)束，否則重復(fù)步驟1～步驟4，直至所有錨節(jié)點(diǎn)都部署優(yōu)化完畢；

（6）當(dāng)錨節(jié)點(diǎn)死亡或有新錨節(jié)點(diǎn)加入時(shí)，重復(fù)步驟1～5直至重新部署優(yōu)化結(jié)束。

錨節(jié)點(diǎn)部署優(yōu)化算法流程如圖4所示。

圖4　錨節(jié)點(diǎn)部署優(yōu)化算法流程圖Fig.4　Flowchart of anchor nodes'optimal deployment

4　仿真分析

在現(xiàn)有的距離無(wú)關(guān)的定位算法中，APIT（Approximate Point-in-Triangulation Test）［9］和DVHOP［10］算法因定位精度較高、定位速度快和無(wú)需測(cè)距等特點(diǎn)，在實(shí)際工程中得到了廣泛應(yīng)用。本文針對(duì)錨節(jié)點(diǎn)部署優(yōu)化前后的網(wǎng)絡(luò)覆蓋率、網(wǎng)絡(luò)連通性進(jìn)行了仿真比較，并使用APIT算法和DV-HOP算法從定位覆蓋率和定位誤差上進(jìn)一步考察了錨節(jié)點(diǎn)部署優(yōu)化后的網(wǎng)絡(luò)性能；為便于仿真結(jié)果的描述，將錨節(jié)點(diǎn)部署優(yōu)化后使用APIT和DV-HOP算法進(jìn)行定位的過程稱為APITANOD算法（APIT base on anchor nodes'optimal deployment）和DV-HOPANOD算法（DV-HOP base on anchor nodes'optimal deployment）。仿真環(huán)境設(shè)計(jì)為實(shí)驗(yàn)室理想環(huán)境下，節(jié)點(diǎn)隨機(jī)分布于仿真空間中。為提高仿真精度、減少測(cè)試誤差，考慮到上位機(jī)運(yùn)算性能，所有仿真結(jié)果經(jīng)過100次獨(dú)立仿真求均值獲得，實(shí)際應(yīng)用中信號(hào)間的相互干擾有可能造成仿真結(jié)果的偏差，需進(jìn)一步在實(shí)際環(huán)境中測(cè)試。仿真區(qū)域?yàn)?00 m×300 m×300 m；未知節(jié)點(diǎn)數(shù)800；錨節(jié)點(diǎn)比例為5%，10%，15%，…，50%；通信半徑r為30 m；彈性系數(shù)c為0.5；長(zhǎng)度系數(shù)η為1。

4.1錨節(jié)點(diǎn)網(wǎng)絡(luò)覆蓋率

錨節(jié)點(diǎn)網(wǎng)絡(luò)覆蓋率即監(jiān)測(cè)區(qū)域被錨節(jié)點(diǎn)覆蓋的百分率，三維空間中將每個(gè)錨節(jié)點(diǎn)的傳感范圍視為一個(gè)以錨節(jié)點(diǎn)為球心的球體，然后使用若干個(gè)覆蓋區(qū)域可重疊的球體覆蓋三維監(jiān)測(cè)區(qū)域的比例，即錨節(jié)點(diǎn)覆蓋率。三維無(wú)線傳感器網(wǎng)絡(luò)中錨節(jié)點(diǎn)網(wǎng)絡(luò)覆蓋率可用以下公式計(jì)算：

式中：Ai為錨節(jié)點(diǎn)i的球形覆蓋區(qū)域；A為整個(gè)監(jiān)測(cè)區(qū)域范圍；r為錨節(jié)點(diǎn)的感知半徑，假設(shè)錨節(jié)點(diǎn)感知半徑與通信半徑相同。錨節(jié)點(diǎn)部署的初始狀態(tài)和經(jīng)過部署優(yōu)化后的網(wǎng)絡(luò)覆蓋率隨錨節(jié)點(diǎn)比例變化曲線如圖5所示。

圖5　錨節(jié)點(diǎn)網(wǎng)絡(luò)覆蓋率比較Fig.5　Comparison of anchor nodes'coverage

從圖5中可以看出，隨著錨節(jié)點(diǎn)比例的增加，部署優(yōu)化前后的網(wǎng)絡(luò)覆蓋率都隨之增加，但由于錨節(jié)點(diǎn)的隨機(jī)部署造成了分布不均勻，增加了覆蓋區(qū)域重疊的現(xiàn)象，因此部署優(yōu)化后的網(wǎng)絡(luò)覆蓋率較優(yōu)化前相比始終較高，體現(xiàn)了算法的優(yōu)越性。

4.2網(wǎng)絡(luò)連通性

無(wú)線傳感器網(wǎng)絡(luò)連通性保證了多跳自組織通信的開展，對(duì)通信、監(jiān)測(cè)和定位等功能有著決定性作用。網(wǎng)絡(luò)連通性是指網(wǎng)絡(luò)中節(jié)點(diǎn)平均擁有的鄰居節(jié)點(diǎn)數(shù)目，即網(wǎng)絡(luò)平均連通度。假設(shè)網(wǎng)絡(luò)中共有N個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)i有Mi個(gè)鄰居節(jié)點(diǎn)，則網(wǎng)絡(luò)平均連通度公式如下：

在不同錨節(jié)點(diǎn)比例下，對(duì)錨節(jié)點(diǎn)部署優(yōu)化前后的網(wǎng)絡(luò)平均連通度進(jìn)行了仿真實(shí)驗(yàn)，結(jié)果如圖6所示。仿真結(jié)果顯示隨著錨節(jié)點(diǎn)比例的增加，錨節(jié)點(diǎn)部署優(yōu)化前后的網(wǎng)絡(luò)平均連通度均隨之增加，但經(jīng)過錨節(jié)點(diǎn)部署優(yōu)化后，網(wǎng)絡(luò)平均連通度在相同錨節(jié)點(diǎn)比例下有所提升。

圖6　網(wǎng)絡(luò)平均連通度比較Fig.6　Comparison of connectivity

4.3定位覆蓋率

定位覆蓋率為已定位節(jié)點(diǎn)與未知節(jié)點(diǎn)總數(shù)的比值，其反映了定位算法對(duì)未知節(jié)點(diǎn)的定位成功率。在不同錨節(jié)點(diǎn)比例下，對(duì)DV-HOPANOD算法、APITANOD算法與錨節(jié)點(diǎn)優(yōu)化前的DV-HOP算法、APIT算法分別進(jìn)行了仿真比較，結(jié)果如圖7所示。

圖7　定位覆蓋率比較Fig.7　Comparison of localization coverage rates

從仿真結(jié)果可以看出，經(jīng)過錨節(jié)點(diǎn)部署優(yōu)化后，DV-HOPANOD算法和APITANOD算法都取得了較高的定位覆蓋率，兩種算法在錨節(jié)點(diǎn)比例大于30%時(shí)，定位覆蓋率上升趨勢(shì)變緩，說(shuō)明錨節(jié)點(diǎn)超過一定比例后，錨節(jié)點(diǎn)數(shù)量的增加對(duì)定位覆蓋率影響減小。

4.4定位誤差

三維無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的定位誤差一般是指節(jié)點(diǎn)實(shí)際位置與估計(jì)位置之間的歐氏距離，為了從整體上考察定位算法的優(yōu)劣，仿真方案采用未知節(jié)點(diǎn)的實(shí)際位置與估計(jì)位置之間的平均誤差值與節(jié)點(diǎn)通信半徑的比值來(lái)衡量定位的精度，即未知節(jié)點(diǎn)的平均定位誤差。假設(shè)未知節(jié)點(diǎn)Ni的實(shí)際坐標(biāo)為（xi，yi，zi），定位算法計(jì)算出的坐標(biāo)為（x′i，y′i，z′i），設(shè)n為未知節(jié)點(diǎn)的數(shù)量，r為節(jié)點(diǎn)的通信半徑，平均定位誤差計(jì)算公式如下：

在不同錨節(jié)點(diǎn)比例下，對(duì)DV-HOPANOD算法、APITANOD算法、DV-HOP算法和APIT算法的平均定位誤差做了仿真比較，結(jié)果如圖8所示。

圖8　定位誤差比較Fig.8　Comparison of location errors

通過仿真結(jié)果可以發(fā)現(xiàn)，三維無(wú)線傳感器網(wǎng)絡(luò)隨機(jī)部署后，由于錨節(jié)點(diǎn)分布的不均勻，特別是DV-HOP算法在根據(jù)錨節(jié)點(diǎn)間的相距跳數(shù)與距離來(lái)估算平均每跳距離時(shí)，造成了較大的誤差，而APIT算法因錨節(jié)點(diǎn)的不均勻分布，造成了算法所需的四面體重疊區(qū)域少，對(duì)該算法的定位精度影響較大。經(jīng)過錨節(jié)點(diǎn)的部署優(yōu)化后，錨節(jié)點(diǎn)分布更加均勻，特別是兼顧了未知節(jié)點(diǎn)密度較大的局部區(qū)域，這些區(qū)域吸引了較多的錨節(jié)點(diǎn)，因此在相同錨節(jié)點(diǎn)比例下，DV-HOPANOD算法和APITANOD算法的定位誤差明顯小于其對(duì)應(yīng)的未優(yōu)化算法。實(shí)驗(yàn)數(shù)據(jù)也反應(yīng)了錨節(jié)點(diǎn)比例的增加對(duì)平均定位誤差影響較大，4種算法都隨錨節(jié)點(diǎn)數(shù)量的增多，定位誤差明顯下降，特別是錨節(jié)點(diǎn)比例在5%～30%時(shí)，定位誤差下降明顯，超過30%后，定位誤差下降趨勢(shì)變緩。在實(shí)際應(yīng)用時(shí)，可根據(jù)網(wǎng)絡(luò)建設(shè)的成本來(lái)選擇合理的錨節(jié)點(diǎn)比例，來(lái)達(dá)到定位精度與網(wǎng)絡(luò)花銷的平衡。

5　結(jié)束語(yǔ)

在三維無(wú)線傳感器網(wǎng)絡(luò)大規(guī)模應(yīng)用中，在監(jiān)測(cè)區(qū)域隨機(jī)拋撒大量傳感器節(jié)點(diǎn)后，極易造成錨節(jié)點(diǎn)的分布不均，嚴(yán)重影響了網(wǎng)絡(luò)的性能。為解決這一問題，本文提出了基于三維彈簧系統(tǒng)模型的錨節(jié)點(diǎn)部署優(yōu)化算法。以往研究?jī)H通過模擬彈簧的伸縮運(yùn)動(dòng)來(lái)對(duì)未知節(jié)點(diǎn)定位，而本文算法通過對(duì)整個(gè)網(wǎng)絡(luò)中的部分錨節(jié)點(diǎn)物理位置調(diào)整，大幅提高現(xiàn)有定位算法的定位精度，無(wú)需另外開發(fā)新的定位算法。仿真結(jié)果表明，該部署優(yōu)化算法提高了錨節(jié)點(diǎn)的網(wǎng)絡(luò)覆蓋率、網(wǎng)絡(luò)連通性和定位覆蓋率，提高了三維環(huán)境下未知節(jié)點(diǎn)的定位精度，為無(wú)線傳感器網(wǎng)絡(luò)的大規(guī)模應(yīng)用提供了一種實(shí)用的、經(jīng)濟(jì)性高的定位技術(shù)。因?qū)嶋H應(yīng)用中電磁環(huán)境復(fù)雜，信號(hào)傳輸時(shí)極易造成干擾，為提高該算法的魯棒性，應(yīng)進(jìn)一步通過實(shí)地測(cè)試來(lái)完善和改進(jìn)算法。

［1］ 趙曉震，田慶戰(zhàn)，孫牧.基于虛擬力驅(qū)動(dòng)的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位［J］.指揮控制與仿真，2012，34（6）：110-114.

ZHAO Xiaozhen，TIAN Qingzhan，SUN Mu.Location method for sensor networks nodes based on virtual force driving［J］.Command Control&Simulation，2012，34（6）：110-114.（in Chinese）

［2］ 劉海波，胡嘯，賈浩.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自身定位算法綜述［J］.電訊技術(shù)，2009，49（2）：80-86.

LIU Haibo，HU Xiao，JIA Hao.Review of node self-localization algorithms in wireless sensor networks［J］.Telecommunication Enginerring，2009，49（2）：80-86.（in Chinese）

［3］ 胡淼，陶正蘇.一種基于可移動(dòng)錨節(jié)點(diǎn)的DV-HOP改進(jìn)定位算法［J］.電子設(shè)計(jì)工程，2011，19（24）：98-101.

HU Miao，TAO Zhengsu.A modified DV-HOP location algorithm based on mobile anchor node［J］.Electronic Design Engineering，2011，19（24）：98-101.（in Chinese）

［4］ STONE K，CAMP T.CAIRN：creating anchors for localization in realistic networks［C］//Proceedings of 2012 IEEE 31st International Conference on Performance Computing and Communications Coference.Austin，TX：IEEE，2012：225-235.

［5］ BROXTON M，LIFTON J，PARADISO J A.Localization on the pushpin computing sensor network using spectral graph drawing and mesh relaxation［J］.SIGMOBILE Mobile Computer&Communication Review，2006，10（1）：1-12.

［6］ 王文韜.應(yīng)急救援場(chǎng)景下定位錨節(jié)點(diǎn)三維模型優(yōu)化部署方法［J］.內(nèi)蒙古師范大學(xué)學(xué)報(bào)，2014，43（2）：180-185.

WANG Wentao.Location nodes three-dimensional deployment in emergency salvage［J］.Journal of Inner Mongolia Normal University，2014，43（2）：180-185.（in Chinese）

［7］ 朱慧勇.基于彈簧模型的無(wú)線傳感器網(wǎng)絡(luò)定位研究［D］.廣州：華南師范大學(xué)，2014.

ZHU Huiyong.The study of localization in wireless sensor networks based on a spring model［D］.Guangzhou：South China Normal University，2014.（in Chinese）

［8］ 陳萬(wàn)明.無(wú)線傳感器網(wǎng)絡(luò)基于彈簧模型的定位算法研究［D］.合肥：中國(guó)科技大學(xué)，2009.

CHEN Wanming.Localization in wireless sensor networks based on a spring model［D］.Hefei：University of Science and Technology of China，2009.（in Chinese）

［9］ 唐明虎，張長(zhǎng)宏，昝風(fēng)彪.無(wú)線傳感器網(wǎng)絡(luò)APIT定位算法［J］.微型機(jī)與應(yīng)用，2010，29（21）：1-4.

TANG Minghu，ZHANG Changhong，ZAN Fengbiao.APIT localization algorithm in wireless sensor networks［J］.Microcomputer and its Applications，2010，29（21）：1-4.（in Chinese）

［10］ 張震，閆連山，劉江濤.基于DV-hop的無(wú)線傳感器網(wǎng)絡(luò)定位算法研究［J］.傳感技術(shù)學(xué)報(bào)，2011，24（10）：1469-1472.

ZHANG Zhen，YAN Lianshan，LIU Jiangtao.Research of positioning technology in Wireless Sensor Network Based on DV-hop［J］.Chinese Journal of Sensors and Actuators，2011，24（10）：1469-1472.（in Chinese）

毛玉明（1980—），男，山東濟(jì)南人，2014年獲博士學(xué)位，現(xiàn)為講師，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)技術(shù)。

MAO Yuming was born in Jinan，Shandong Province，in 1980.He received the Ph.D.degree in 2014.He is now a lecturer.His research concerns wireless sensor networks.

Email：18660106266@163.com

Optimal Deployment of Anchor Nodes Based on 3D Spring Model System

MAO Yuming
（School of Information Science and Electrical Engineering，Shandong Jiaotong University，Jinan 264200，China）

This paper proposes an optimal deployment algorithm of anchor nodes based on spring model system.The optimal deployment algorithm can improve location accuracy for randomly distributed three dimensional（3D）wireless sensor networks，and the anchor nodes'distribution is more reasonable.The algorithm abstracts the relationship of anchor nodes into dots and springs，and anchor nodes do concertina motion by the resultant force.Approximate point-in-triangulation test（APIT）algorithm and approximate point-intriangulation test（DV-HOP）algorithm are used to verify the optimized wireless sensor network.The simulation results show that the anchor nodes'network coverage and localization coverage are wider，and the connectivity of networks is better，and the positioning accuracy is higher.

wireless sensor network；spring model system；anchor node；optimal deployment

1　引 言

錨節(jié)點(diǎn)的部署優(yōu)化是無(wú)線傳感器網(wǎng)絡(luò)研究熱點(diǎn)之一，通過錨節(jié)點(diǎn)的部署優(yōu)化，能有效利用有限網(wǎng)絡(luò)資源，降低網(wǎng)絡(luò)構(gòu)建成本，提高網(wǎng)絡(luò)覆蓋范圍及質(zhì)量，延長(zhǎng)網(wǎng)絡(luò)的生存周期等［1］。目前，無(wú)線傳感器網(wǎng)絡(luò)錨節(jié)點(diǎn)的部署優(yōu)化主要分為兩個(gè)研究方向：一是為了使無(wú)線傳感器網(wǎng)絡(luò)更好地覆蓋感知區(qū)域；二是為了使錨節(jié)點(diǎn)的分布更加合理，提高未知節(jié)點(diǎn)的定位精度［2］。目前大部分研究成果集中于提高網(wǎng)絡(luò)覆蓋率上，而很少利用錨節(jié)點(diǎn)的部署優(yōu)化來(lái)提高定位精度。對(duì)于無(wú)線傳感器網(wǎng)絡(luò)定位研究來(lái)說(shuō)，錨節(jié)點(diǎn)的部署和網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是首先需要研究的問題，是定位算法的研究基礎(chǔ)。

The Natural Science Foundation of Shandong Province（BS2015DX007）；The Open Research Fund from Shandong Provincial Key Laboratory of Computer Network（2015001）

**通信作者:18660106266@163.com 18660106266@163.com

TN929.5；TP212.9

A

1001-893X（2016）08-0850-06

10.3969/j.issn.1001-893x.2016.08.004

2016-03-30；

2016-06-27

date:2016-03-30；Revised date:2016-06-27

山東省自然科學(xué)基金資助項(xiàng)目（BS2015DX007）；山東省計(jì)算機(jī)網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室開放課題（2015001）

引用格式:毛玉明.應(yīng)用三維彈簧系統(tǒng)模型的錨節(jié)點(diǎn)部署優(yōu)化［J］.電訊技術(shù)，2016，56（8）：850-855.［MAO Yuming.Optimal deployment of anchor nodes based on 3D spring model system［J］.Telecommunication Engineering，2016，56（8）：850-855.］