張 華,姚嘉鑫,吳朝云

（1.四川旅游學(xué)院信息技術(shù)系，四川 成都 610100；2.電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，四川 成都 611731）

傳感器網(wǎng)絡(luò)移動(dòng)中繼節(jié)點(diǎn)部署算法

張 華1,姚嘉鑫1,吳朝云2

（1.四川旅游學(xué)院信息技術(shù)系，四川 成都 610100；2.電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，四川 成都 611731）

針對(duì)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量有限性及節(jié)點(diǎn)能量消耗不勻性問題，提出一種移動(dòng)中繼節(jié)點(diǎn)部署算法。首先假設(shè)網(wǎng)絡(luò)中沒有移動(dòng)中繼節(jié)點(diǎn)時(shí)，對(duì)靜態(tài)節(jié)點(diǎn)提出一種最優(yōu)路由樹算法來構(gòu)建數(shù)據(jù)傳輸路徑；在此基礎(chǔ)上再采用貪婪算法增加移動(dòng)節(jié)點(diǎn)改善網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)提高路由樹連通性；接著提出一種高效的分布式迭代算法，使得路由樹的拓?fù)浣Y(jié)構(gòu)收斂于最優(yōu)位置；最后進(jìn)行理論分析與仿真實(shí)驗(yàn)，結(jié)果表明該方法具有一定理論意義與實(shí)用價(jià)值。

傳感器網(wǎng)絡(luò)；移動(dòng)中繼節(jié)點(diǎn)；壽命；貪婪算法

0 引 言

隨著網(wǎng)絡(luò)技術(shù)的進(jìn)步和物聯(lián)網(wǎng)的發(fā)展，無線傳感器節(jié)點(diǎn)在各種監(jiān)測(cè)中得到應(yīng)用，如現(xiàn)代農(nóng)業(yè)、林業(yè)、氣象、環(huán)境、家居等[1-2]。由于傳感器節(jié)點(diǎn)的存儲(chǔ)容量有限，所采集的各種數(shù)據(jù)需要發(fā)送到基站進(jìn)行存取和分析，而在傳感器能量消耗的各個(gè)環(huán)節(jié)中，發(fā)送數(shù)據(jù)消耗能量最大，數(shù)據(jù)密集型無線傳感器網(wǎng)絡(luò)面臨的主要挑戰(zhàn)是減少傳感器節(jié)點(diǎn)的能量消耗，對(duì)節(jié)能研究具有重大的意義。

一些學(xué)者利用節(jié)點(diǎn)的移動(dòng)性，提出了一些降低無線傳感器網(wǎng)絡(luò)能量消耗的算法[3-12]。如移動(dòng)節(jié)點(diǎn)可以通過機(jī)器人方式來回移動(dòng)收集靜態(tài)節(jié)點(diǎn)傳遞的數(shù)據(jù)[3-5]，再通過單跳或者多跳方式把相關(guān)數(shù)據(jù)發(fā)送給使用終端或者中心服務(wù)器[6-7]。另外移動(dòng)節(jié)點(diǎn)也可以被用來作為中繼器，轉(zhuǎn)發(fā)從源節(jié)點(diǎn)到基站的數(shù)據(jù)，文獻(xiàn)[8-9]專門研究了移動(dòng)中繼器的運(yùn)動(dòng)策略。以

上文獻(xiàn)的移動(dòng)節(jié)點(diǎn)能量供應(yīng)方式存在一些問題。首先在網(wǎng)絡(luò)的總體能量消耗中沒有考慮移動(dòng)節(jié)點(diǎn)運(yùn)動(dòng)時(shí)所消耗的能量，通常的做方法是認(rèn)為移動(dòng)節(jié)點(diǎn)的能量是有補(bǔ)充的[4]，在現(xiàn)實(shí)情況中，這并不總是可行的（如物理環(huán)境的限制）；再就是認(rèn)為移動(dòng)節(jié)點(diǎn)的計(jì)算能力是萬能的，可以反復(fù)計(jì)算最優(yōu)運(yùn)動(dòng)路徑和改變它們的位置、方向、移動(dòng)速度[4-5，10-11]。這種能力通常在現(xiàn)有低成本的移動(dòng)傳感器平臺(tái)難以提供支持，例如，使用8位CPU和小電池供電Robomote[12]節(jié)點(diǎn)最多只能夠運(yùn)動(dòng)25min。

針對(duì)以上問題，本文使用一次性廉價(jià)的移動(dòng)中繼來實(shí)現(xiàn)以上功能，并減少傳感器網(wǎng)絡(luò)的總體能量消耗。思路為移動(dòng)節(jié)點(diǎn)沿著從基站到數(shù)據(jù)收集節(jié)點(diǎn)的路徑移動(dòng)到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)需要連通的位置，然后保持靜止，這樣通信延遲可以得到顯著提高，且每個(gè)移動(dòng)節(jié)點(diǎn)不像其他算法需要反復(fù)重定位。在整個(gè)算法中，先比較了不同的初始樹的構(gòu)建方法，提出一種最佳的樹的構(gòu)建策略，再設(shè)計(jì)移動(dòng)中繼節(jié)點(diǎn)的插入算法及路由樹的優(yōu)化算法，最后對(duì)現(xiàn)有的移動(dòng)中繼節(jié)點(diǎn)和靜態(tài)傳感器能量模型平臺(tái)為基礎(chǔ)進(jìn)行了大量的仿真。

1 問題定義

1.1 能量消耗模型

移動(dòng)傳感器節(jié)點(diǎn)能量消耗主要體現(xiàn)在發(fā)送或者接收數(shù)據(jù)、計(jì)算和移動(dòng)3個(gè)方面，其中通信和移動(dòng)是能量消耗的主要環(huán)節(jié)。而對(duì)節(jié)點(diǎn)的各種狀態(tài)而言，空閑偵聽、休眠調(diào)度也是消耗能量重要的組成部分[13]，本文將重點(diǎn)放在減少數(shù)據(jù)傳輸和節(jié)點(diǎn)移動(dòng)的能量消耗，通過移動(dòng)中繼器作為靜態(tài)節(jié)點(diǎn)數(shù)據(jù)的轉(zhuǎn)發(fā)節(jié)點(diǎn)，來減少總體能量的消耗。移動(dòng)中繼傳感器節(jié)點(diǎn)選擇采用差分驅(qū)動(dòng)器技術(shù)的輪式傳感器節(jié)點(diǎn)（如Khepera[14]，Robomote[12]和FIRA[15]），這種類型的節(jié)點(diǎn)通常有兩個(gè)輪子，每個(gè)輪子由獨(dú)立的發(fā)動(dòng)機(jī)控制。能量模型采用文獻(xiàn)[15]所提出的移動(dòng)單位距離消耗模型，為中繼節(jié)點(diǎn)移動(dòng)時(shí)消耗的能量，如式（1）所示。

式中：EM（d）——中繼節(jié)點(diǎn)M移動(dòng)距離d所消耗的能量；

k——參數(shù)，主要由節(jié)點(diǎn)移動(dòng)的速度決定。

在文獻(xiàn)[15]中，作者對(duì)節(jié)點(diǎn)移動(dòng)速度與能量消耗關(guān)系作了專門研究，當(dāng)k取值為2時(shí)，達(dá)到最優(yōu)值。數(shù)據(jù)傳輸能量消耗模型，如式（2）所示。

式中：ET（d）——節(jié)點(diǎn)T發(fā)送數(shù)據(jù)到達(dá)距離d的地方所消耗的能量；

m——發(fā)送數(shù)據(jù)包的大??；

a，b——參數(shù)，由環(huán)境因數(shù)決定。

1.2 數(shù)學(xué)模型

假定所有的動(dòng)作都是在網(wǎng)絡(luò)收集數(shù)據(jù)傳輸開始前完成，并沒有障礙影響變速器的工作。同時(shí)，假設(shè)所有的移動(dòng)節(jié)點(diǎn)知道自己的起始位置，都安裝GPS單元為網(wǎng)絡(luò)定位提供服務(wù)，每個(gè)移動(dòng)節(jié)點(diǎn)和移動(dòng)相應(yīng)的距離都不超過移動(dòng)中繼器預(yù)定范圍，此外在移動(dòng)節(jié)點(diǎn)更改網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)時(shí)，不考慮網(wǎng)絡(luò)短暫的延遲。本文面向的是一個(gè)2D平面（R2），但其結(jié)果可應(yīng)用在R3、R4、多維平面。

問題描述如下：整個(gè)網(wǎng)絡(luò)由3部分節(jié)點(diǎn)組成，一個(gè)或者多個(gè)數(shù)據(jù)匯聚節(jié)點(diǎn)，大量的移動(dòng)中繼節(jié)點(diǎn)和大量的靜態(tài)數(shù)據(jù)采集節(jié)點(diǎn)。從數(shù)據(jù)匯聚節(jié)點(diǎn)開始構(gòu)造一個(gè)方向路由樹，同時(shí)在這個(gè)靜態(tài)的方向性路由樹里面插入移動(dòng)中繼節(jié)點(diǎn)對(duì)路由結(jié)構(gòu)樹優(yōu)化，使得數(shù)據(jù)在傳輸中網(wǎng)絡(luò)的能量消耗最少。整個(gè)網(wǎng)絡(luò)可定義如下：S={s1，s2，s3，…，sn}表示整個(gè)網(wǎng)絡(luò)中的n個(gè)節(jié)點(diǎn)，O={o1，o2，o3，…，on}表示整個(gè)網(wǎng)絡(luò)中可放置節(jié)點(diǎn)的n個(gè)位置，oi是節(jié)點(diǎn)si的初始位置，且滿足條件i∈（1，…，n）；整個(gè)網(wǎng)絡(luò)的能量消耗主要由兩部分組成，節(jié)點(diǎn)移動(dòng)消耗的能量加上數(shù)據(jù)傳送的能量，如式（3）所示。

其中c（＜E，U＞）表示整個(gè)網(wǎng)絡(luò)能量的消耗，它由兩部分組成：E為構(gòu)架方向性路中樹移動(dòng)節(jié)點(diǎn)S移動(dòng)時(shí)所需要消耗的能量；U表示各位置節(jié)點(diǎn)傳輸數(shù)據(jù)時(shí)消耗能量。根據(jù)上面的定義，把相關(guān)符號(hào)代入式（3），整個(gè)網(wǎng)絡(luò)的能量消耗數(shù)學(xué)模型如式（4）所示。其中式（4）表示由第i個(gè)節(jié)點(diǎn)移動(dòng)至第j個(gè)節(jié)點(diǎn)過程中系統(tǒng)消耗的總能量。

2 移動(dòng)中繼節(jié)點(diǎn)部署算法

最佳移動(dòng)中繼配置問題依賴多種因素，如路由樹的拓?fù)浣Y(jié)構(gòu)及通過每個(gè)鏈路傳送的數(shù)據(jù)量。當(dāng)傳送小數(shù)據(jù)時(shí)，最佳的配置位置是中繼節(jié)點(diǎn)在它們的原始位置，這樣就不會(huì)產(chǎn)生中繼節(jié)點(diǎn)移動(dòng)消耗的能量；傳輸?shù)臄?shù)據(jù)量大時(shí)，不能再采用此方法，會(huì)導(dǎo)致節(jié)點(diǎn)能量過早用盡，因此需要添加新的中繼節(jié)點(diǎn)，改變拓?fù)浣Y(jié)構(gòu)來達(dá)到節(jié)能的效果，而中繼節(jié)點(diǎn)移動(dòng)到什么位置才最節(jié)能是需要解決的主要問題。解決的方法分為3步：首先不考慮中繼節(jié)點(diǎn)，按照能量傳輸模型建立路由

樹；再根據(jù)數(shù)據(jù)量的大少?zèng)Q定是否插入中繼節(jié)點(diǎn)及插入在什么位置；最后對(duì)拓?fù)渎酚蓸溥M(jìn)行處理。

2.1 靜態(tài)路由樹構(gòu)造

利用最短路徑樹方法來構(gòu)建路由樹的拓?fù)浣Y(jié)構(gòu)，首先以通信能量消耗模型為依據(jù)定義一個(gè)通信權(quán)值w，從而可得到在網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)si，sj傳遞數(shù)據(jù)時(shí)所消耗的能量值，如式（5）所示。

以Sink節(jié)點(diǎn)為中心，以式（5）為基礎(chǔ)尋找最近的節(jié)點(diǎn)加入到路由結(jié)構(gòu)樹集合S′中，再以集合S′為基礎(chǔ)，添加其他節(jié)點(diǎn)，一直到所有節(jié)點(diǎn)加入為止，具體過程如圖1所示。

2.2 移動(dòng)中繼節(jié)點(diǎn)的插入及路由樹的優(yōu)化

利用貪婪算法添加節(jié)點(diǎn)來改造靜態(tài)路由樹的拓?fù)浣Y(jié)構(gòu)，定義Sout={sout，1，sout，2，…，sout，n}為移動(dòng)中繼節(jié)點(diǎn)的集合，且不在靜態(tài)路由樹的節(jié)點(diǎn)中。如果靜態(tài)節(jié)點(diǎn)si，sj之間需要增加一個(gè)中繼來轉(zhuǎn)發(fā)數(shù)據(jù)，定義最理想位置為O（x，y）。需要對(duì)加入中繼節(jié)點(diǎn)前后的能量消耗進(jìn)行對(duì)比，如果優(yōu)于前，則加入中繼節(jié)點(diǎn)，否則不加入，如式（6）～式（8）所示。

式（6）主要是用來計(jì)算不插入中繼節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)si向節(jié)點(diǎn)sj發(fā)送mi，j個(gè)數(shù)據(jù)包所消耗的能量，式（7）為計(jì)算插入中繼節(jié)點(diǎn)后所消耗的能量，式（8）主要用來比較哪種方式更節(jié)能。如果式（8）大于“0”則插入中繼節(jié)點(diǎn)，否則不插入。

經(jīng)過式（8）計(jì)算后，兩個(gè)節(jié)點(diǎn)之間能夠找節(jié)能的路由方式，但在整個(gè)網(wǎng)絡(luò)中可能出現(xiàn)有多個(gè)節(jié)點(diǎn)靠近移動(dòng)中繼節(jié)點(diǎn)，如何使整個(gè)網(wǎng)絡(luò)節(jié)能，這是下一步對(duì)路由樹的優(yōu)化問題。首先如式（9）所示對(duì)mi進(jìn)行計(jì)算，同時(shí)計(jì)算所有可能的路徑，并分別求X軸、Y軸偏導(dǎo)數(shù)，并設(shè)他們的結(jié)果為“0”，如式（10）～式（11）所示。

其中A，Bx，By取值如式（12）～式（14）所示。

3 仿真實(shí)驗(yàn)及測(cè)試

在整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)中，隨機(jī)產(chǎn)生100個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，每個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中存在100個(gè)節(jié)點(diǎn)，覆蓋面積為150m×150m的區(qū)域，每個(gè)區(qū)域存在1個(gè)Sink節(jié)點(diǎn)及10～20個(gè)隨機(jī)的移動(dòng)中繼節(jié)點(diǎn)。取各種結(jié)果的平均值為測(cè)試結(jié)果。先測(cè)試傳送數(shù)據(jù)量的改變對(duì)算法的影響，再測(cè)試移動(dòng)中繼節(jié)點(diǎn)移動(dòng)距離改變對(duì)算法的影響，最后測(cè)試兩者都改變對(duì)算法的影響。

移動(dòng)中繼的距離是自動(dòng)計(jì)算出來的，在整個(gè)測(cè)試中不好改變，所以設(shè)計(jì)的方案為改變其節(jié)點(diǎn)的數(shù)量，移動(dòng)節(jié)點(diǎn)數(shù)量從4個(gè)增加到20個(gè)，每個(gè)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包的大小為1～150MB。在環(huán)境配置方面，令a= 0.6×10-7，b=4×10-10，作為環(huán)境配置。移動(dòng)中繼節(jié)點(diǎn)的設(shè)置分為兩步，先令k=2，再分別令k=1，2，4[13-15]。由于本文所提出的是一種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的優(yōu)化方案，為了便于比較，采用常用的3種路由算法（powerbased、hop-based、greedy geographic）來測(cè)試網(wǎng)絡(luò)的性能。power-based路由算法（簡稱pb）為Sink節(jié)點(diǎn)到數(shù)據(jù)收集節(jié)點(diǎn)最短距離路徑傳遞算法，所消耗的

能量為數(shù)據(jù)傳遞時(shí)節(jié)點(diǎn)之間傳送的能量消耗和。hop-based路由算法（簡稱hb）為Sink節(jié)點(diǎn)到數(shù)據(jù)收集節(jié)點(diǎn)最少跳數(shù)的路徑為路由路徑。greedy geographic路由算法（簡稱gg）為貪婪路由算法，在通信范圍內(nèi)每次選擇到達(dá)Sink節(jié)點(diǎn)最近的節(jié)點(diǎn)為傳送數(shù)據(jù)節(jié)點(diǎn)。

圖2為采用本網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)后，能量消耗與以前pb、hb、gg采用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)能量消耗情況的比較。從圖2中可以看出，在傳輸少量數(shù)據(jù)時(shí)，pb以前采用的模型與本文提出的模型能量消耗一樣，hb,gg則要優(yōu)于本文方法，主要原因在于，這個(gè)模型需要移動(dòng)中繼節(jié)點(diǎn)，因此需要消耗能量；當(dāng)數(shù)據(jù)量大時(shí)，采用提出的模型比其他的模型要節(jié)能很多，當(dāng)數(shù)據(jù)過150MB時(shí)，節(jié)能量超過40%。

圖3為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)模型優(yōu)化前后能量消耗對(duì)比。可以看出數(shù)據(jù)量少時(shí)，能量節(jié)約值不大，當(dāng)數(shù)據(jù)量超過150MB時(shí)，能量可節(jié)約70%左右。從圖2、圖3中可以看出，不管是pb、hb、gg哪一種路由算法，當(dāng)長時(shí)間收集數(shù)據(jù)且是收集大量數(shù)據(jù)時(shí)，本文所提出來的模型優(yōu)于同類型的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

圖4、圖5是隨中繼節(jié)點(diǎn)數(shù)量的增長k取不同值集中式算法與分布式算法能量消耗情況分析，圖4與圖5都說明了當(dāng)k的值越大，則節(jié)約的能量越少，k的值越小，則節(jié)約的能量越多；同時(shí)也發(fā)現(xiàn)分布式算法最大節(jié)能量只是以前的50%，而集中式算法最多可以節(jié)約能量60%，且k取相同值時(shí)集中式算法節(jié)約能量要比分布式算法多。經(jīng)過原因分析及結(jié)果追蹤知道，采用分布式算法本身消耗的能量比較低，所以不管采用什么辦法都很難再節(jié)能太多，在整個(gè)能量消耗方面分布式算法的能量消耗要低于集中式算法。

4 結(jié)束語

本文提出利用移動(dòng)中繼器節(jié)點(diǎn)來改善網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，從而全面減少網(wǎng)絡(luò)的總能量消耗。當(dāng)整個(gè)網(wǎng)絡(luò)中沒有移動(dòng)中繼節(jié)點(diǎn)時(shí)，先提出一種最優(yōu)路由樹算法，構(gòu)造一個(gè)網(wǎng)絡(luò)路由樹，再采用貪婪算法增加移動(dòng)節(jié)點(diǎn)改善網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)提高了路由樹連通性，接著提出高效的分布式迭代算法，使得路由樹的拓?fù)浣Y(jié)構(gòu)收斂于最優(yōu)位置，最后進(jìn)行理論分析與仿真實(shí)驗(yàn)，結(jié)果表明有一定理論意義與實(shí)用價(jià)值。

[1]Szewczyk R，Mainwaring A，Polastre J，et al.An Analysis of a large scale habitat monitoring application[C]∥ Poc second ACM Conf on Embedded Networked Sensor Systems，2004.

[2]Luo L，Cao Q，Huang C，et al.EnviroMic：towards cooperative storage and retrieval in audio sensor networks[C]∥ Proc 27th Int’l ConfDistributed Omputing Systems，2007.

[3]鄔厚民.無線傳感網(wǎng)絡(luò)中能量和距離改良的LEACH分簇算法[J].中國測(cè)試，2012，38（5）：62-65，101.

[4]Kansal A，Jea D D，Estrin D，et al.Controllably mobile infrastructure for low energy embedded networks[J]. IEEE Trans Mobile Computing，2006，5（8）：958-973.

[5]Xing G，Wang T，Jia W，et al.Rendezvous design algorithmsfor wirelesssensor networks with amobile base station[J].Proc ACM Mobihoc，2008：231-240.

[6]Shah R，Roy S，Jain S，et al.Data mules：modeling a three-tier architecture for sparse sensor networks[C]∥Proc IEEE First Int’l Workshop Sensor Network Protocols and Applications，2003.

[7]Jain S，Shah R，Brunette W，et al.Exploiting mobility for energy efficient data collection in wireless sensor networks[J].Mobile Networks and Applications，2006，11（1）：327-339.

[8]Wang W，Srinivasan V，Chua K C.Using mobile relays to prolong the lifetime of wireless sensor networks[C]∥Proc ACM Mobicom.Cologne，2005.

[9]Goldenberg D K，Lin J，Morse A S.Towards mobility as a network control primitive[C]∥ Proc ACM Mobihoc，2004：163-174.

[10]Somasundara A A，Ramamoorthy A，Srivastava M B. Mobile element scheduling with dynamic deadlines[J]. IEEE Trans Mobile Computing，2007，6（4）：395-410.

[11]Gu Y，Bozdag D，Ekici E.Mobile element based differentiated message delivery in wireless sensor networks [C]∥Proc Int’l Symp World of Wireless,Mobile and Multimedia Networks，2006.

[12]Dantu K，Rahimi M，Shah H，et al.Robomote：enabling mobility in sensor networks[C]∥Proc Fourth Int’l Conf.Information Processing in Sensor Networks，2005.

[13]Wang L，Xiao Y.A survey of energy-efficient scheduling mechanisms in sensor networks[J].Mobile Networks and Applications，2006（11）：723-740.

[14]Kim J H，Kim D H，Kim Y J，et al.Soccer robotics[M]. Germany：Springer，2004.

[15]Wang G，Irwin M J，Berman P，et al.Optimizing sensor movement planning for energy efficiency[C]∥Proc Int’l Symp Low Power Electronics and Design，2005：215-220.

4 結(jié)束語

從理論分析和試驗(yàn)結(jié)果可以看出，通過多個(gè)濾波器的并行拼接達(dá)到了提升濾波器速度的效果，現(xiàn)有方法設(shè)計(jì)的濾波器在FPGA中可以實(shí)現(xiàn)200～300MHz的工作速度。按本文的方法，如果P=4，則可以使最終濾波器的速度達(dá)到800～1200MHz，其速度達(dá)到了成倍增加的效果，如果再增加P值，會(huì)進(jìn)一步提升FIR濾波器的速率，也為將來更加廣泛的應(yīng)用奠定了堅(jiān)實(shí)的基礎(chǔ)。

參考文獻(xiàn)

[1]Ludwig R，Bogdanov G.射頻電路設(shè)計(jì)：理論與應(yīng)用[M].北京：電子工業(yè)出版社，2005：192-194.

[2]陳樹新.數(shù)字信號(hào)處理[M].北京：高等教育出版社，2005：45-46.

[3]趙文亮，蔣冰.基于FPGA的高階高速FIR濾波器設(shè)計(jì)與實(shí)現(xiàn)[J].中國有線電視，2006（3-4）：329-331.

[4]湯寧生，黃建國，王志剛.一種200 MHz處理速度的FIR濾波器設(shè)計(jì)[J].微計(jì)算機(jī)信息，2007（3）：183-187.

[5]楊鴻武，丁朋程，王全州.基于FPGA的高速全并行FIR濾波器的設(shè)計(jì)[J].西北師范大學(xué)學(xué)報(bào)，2012，48（1）：48-51.

[6]何子述，夏威.現(xiàn)代數(shù)字信號(hào)處理及其應(yīng)用[M].北京：清華大學(xué)出版社，2009：28-91.

[7]劉凌，胡永生.數(shù)字信號(hào)處理FPGA實(shí)現(xiàn)[M].北京：清華大學(xué)出版社，2003：251-252.

[8]張維良，張彧，楊再初，等.高速并行FIR濾波器的FPGA實(shí)現(xiàn)[J].系統(tǒng)工程與電子技術(shù)，2009，31（8）：1819-1822.

Deploy algorithm of mobile relay nodes of sensor network

ZHANG Hua1，YAO Jia-xin1，WU Chao-yun2
（1.Department of Information Technology，Sichuan Tourism University，Chengdu 610100，China；2.School of Computer Science and Engineering，University of Electronic Science and Technology，Chengdu 611731，China）

For the problems of the limitation of node energy and the imbalance of energy consumption in the sensor network，this paper puts forward a deploy algorithm of mobile relay nodes.Firstly，on the condition that there are no mobile relay nodes in the network，the optimal route tree algorithm to construct data transmission route for static nodes has been put forward;on the basis of previous research，with the help of greedy algorithm more mobile nodes are added to the route trees so as to improve the typology structure of network and to work on the connectivity of route trees；then a high efficient distributive iterative algorithm is proposed to put the typology structure of the route trees in the optimal position；finally theoretical analysis and simulated experiment manifest that this algorithm is of theoretical meaning and practical value in one sense.

sensor network；mobile relay nodes；life；gready algorithm

TP212；TP301.6；TN911.7；TP391.9

：A

：1674-5124（2014）04-0078-05

10.11857/j.issn.1674-5124.2014.04.020

2013-12-17；

：2014-02-25

四川省教育廳重點(diǎn)項(xiàng)目（12ZA280）

張 華（1977-），男，四川富順縣人，副教授，碩士，研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)。