基于時間同步的無線傳感器網(wǎng)絡(luò)覆蓋控制優(yōu)化算法

1、收稿日期:2011-04-04;修回日期:2011-07-18基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(6077683460870010作者簡介:常光強(qiáng)(1986-,男,山東濰坊人,碩士研究生,主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)(chgq0307163com ;樊曉平(1961-,男,教授,博導(dǎo),主要研究方向?yàn)橹悄苄畔⑻幚?、信號處理?劉少強(qiáng)(1964-,男,副教授,博士,主要研究方向?yàn)閭鞲衅骷爸悄軝z測技術(shù)、無線傳感器網(wǎng)絡(luò)基于時間同步的無線傳感器網(wǎng)絡(luò)覆蓋控制優(yōu)化算法*常光強(qiáng),樊曉平,劉少強(qiáng)(中南大學(xué)信息科學(xué)與工程學(xué)院,長沙410001摘要:為了實(shí)現(xiàn)網(wǎng)絡(luò)覆蓋控制的優(yōu)化,減少能耗,提出了一種分布的、高效節(jié)能、

2、與節(jié)點(diǎn)位置無關(guān)的傳感器網(wǎng)絡(luò)覆蓋算法。在該算法中,節(jié)點(diǎn)與鄰居交換信息,并通過能量大小競選工作節(jié)點(diǎn),節(jié)點(diǎn)根據(jù)自身與工作節(jié)點(diǎn)的距離判斷決定進(jìn)入工作狀態(tài)或休眠狀態(tài),并采用在生成樹中廣播時間同步算法使工作節(jié)點(diǎn)網(wǎng)絡(luò)達(dá)到時間同步。仿真結(jié)果比較表明,該算法能夠明顯減少工作節(jié)點(diǎn)數(shù),從而減少能量消耗,延長網(wǎng)絡(luò)壽命。關(guān)鍵詞:無線傳感器網(wǎng)絡(luò);覆蓋問題;與位置無關(guān);覆蓋優(yōu)化中圖分類號:TP393;TP301.6文獻(xiàn)標(biāo)志碼:A文章編號:1001-3695(201201-0035-03doi :103969/jissn1001-3695201201009Coverage control optimization algor

3、ithm in wireless sensor networks ontime synchronizationCHANG Guang-qiang ,FAN Xiao-ping ,LIU Shao-qiang(College of Information Science Engineering ,Central South University ,Changsha 410001,China Abstract :In order to achieve optimal control of network coverage ,reduce energy consumption ,this paper

4、 presented a distrib-uted ,energy efficient ,and the node position independent of the sensor network coverage algorithmIn the algorithm ,nodes exchanged information with neighbors and worked through the energy of running nodes ,other nodes according to their distance from the node with the work ,mad

5、e judgments ,or to enter the work state ,or into sleep stateSimulation results show that thealgorithm can significantly reduce the number of nodes working ,thus to reduce energy consumption and prolong network life-timeKey words :wireless sensor networks (WSN ;coverage problem ;location-unaware ;cov

6、erage optimization0引言無線傳感器網(wǎng)絡(luò)(wireless sensor network ,WSN 的覆蓋控制,就是在傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量、無線網(wǎng)絡(luò)通信帶寬、網(wǎng)絡(luò)計算處理能力等資源普遍受限的情況下,通過網(wǎng)絡(luò)傳感器節(jié)點(diǎn)放置以及路由選擇等手段,最終使無線傳感器網(wǎng)絡(luò)的各種資源得到優(yōu)化分配。選擇合適的無線傳感器網(wǎng)絡(luò)覆蓋控制策略,有助于網(wǎng)絡(luò)節(jié)點(diǎn)能量的有效控制、感知服務(wù)質(zhì)量的提高和整體生存時間的延長1 3。作為一種分布式系統(tǒng),WSN 時間同步是至關(guān)重要的。時間同步為建立許多WSN 的應(yīng)用提供了基礎(chǔ)的服務(wù)。例如,傳感器節(jié)點(diǎn)間的協(xié)調(diào)和協(xié)作需要時間同步。傳感器節(jié)點(diǎn)需要在同一時刻休眠和喚醒,否則多個

7、節(jié)點(diǎn)同時進(jìn)入休眠狀態(tài)會使網(wǎng)絡(luò)出現(xiàn)盲區(qū)。近年來已有一些學(xué)者開展了WSN 優(yōu)化覆蓋控制方面的研究工作,并取得了一定的進(jìn)展。Ye 等人4提出了基于探測(probing 的密度控制算法PEAS 。PEAS 算法要求每個睡眠節(jié)點(diǎn)定期地在其探測范圍內(nèi)探測鄰居節(jié)點(diǎn)的狀態(tài),若在其探測范圍內(nèi)沒有工作節(jié)點(diǎn),則進(jìn)入工作狀態(tài);否則仍處于睡眠狀態(tài)。顯然,PEAS 算法中的某些節(jié)點(diǎn)可能持續(xù)工作,導(dǎo)致過早死亡,由于網(wǎng)絡(luò)中的節(jié)點(diǎn)能耗不均勻?qū)⒂绊懜采w質(zhì)量。Zhang 等人在文獻(xiàn)5中討論了網(wǎng)絡(luò)覆蓋和連通性,提出了一種分布式的節(jié)點(diǎn)密度控制算法OGDC ,算法要求節(jié)點(diǎn)根據(jù)其鄰居信息和自己的位置信息計算與鄰居節(jié)點(diǎn)的覆蓋關(guān)系。Xu 等人

8、在文獻(xiàn)6中提出了GAF (geographical adaptive fidelity 算法。在GAF 算法中,每個節(jié)點(diǎn)根據(jù)其位置信息將整個區(qū)域劃分為若干個虛擬單元格(grid ,其大小必須保證相鄰格子中任何一對節(jié)點(diǎn)可以直接通信。但是GAF 算法沒有考慮到實(shí)際網(wǎng)絡(luò)中節(jié)點(diǎn)之間距離的鄰近并不能代表節(jié)點(diǎn)之間可以直接通信的問題,也不能保證節(jié)點(diǎn)能耗均勻。毛鶯池等人在文獻(xiàn)7中提出了DELIC 協(xié)議,協(xié)議中的節(jié)點(diǎn)與鄰居交換信息,并通過能量大小競選工作節(jié)點(diǎn),其他未競選成功的節(jié)點(diǎn)關(guān)閉通信設(shè)備。目前的大部分覆蓋控制算法都需要節(jié)點(diǎn)的精確位置信息以計算節(jié)點(diǎn)間的覆蓋關(guān)系,在選取活動過程中產(chǎn)生較大的計算和控制開銷。本文主

9、要研究了時間同步以及與位置無關(guān)的無線傳感器網(wǎng)絡(luò)優(yōu)化覆蓋控制策略,無須節(jié)點(diǎn)的位置信息,從而減少了整個網(wǎng)絡(luò)額外的能量消耗。1網(wǎng)絡(luò)模型的建立和問題陳述1.1網(wǎng)絡(luò)模型的建立假設(shè)N 個傳感器節(jié)點(diǎn)隨機(jī)均勻地部署在一個L L 的二維正方形區(qū)域M 內(nèi),節(jié)點(diǎn)密度要求足夠大,當(dāng)所有傳感器節(jié)點(diǎn)都處于工作狀態(tài)時,能夠?qū)φ麄€區(qū)域完全覆蓋且整個網(wǎng)絡(luò)是連第29卷第1期2012年1月計算機(jī)應(yīng)用研究Jan.2012通的,并假設(shè)該無線傳感器網(wǎng)絡(luò)具有以下性質(zhì):a 節(jié)點(diǎn)部署方式。節(jié)點(diǎn)是同構(gòu)的,節(jié)點(diǎn)采用隨機(jī)部署,且部署后節(jié)點(diǎn)不能移動。b 節(jié)點(diǎn)通信范圍。相對于節(jié)點(diǎn)感知范圍而言,監(jiān)測區(qū)域M 足夠大(Rs L ,邊界因素可以忽略。c 節(jié)點(diǎn)感

10、知模型。節(jié)點(diǎn)采用布爾感知模型,即每個節(jié)點(diǎn)的感知范圍是以節(jié)點(diǎn)為圓心、傳感半徑Rs 為半徑的圓,在感知范圍內(nèi)的所有節(jié)點(diǎn)都可以被感知,否則不被感知。d 節(jié)點(diǎn)位置信息。每個節(jié)點(diǎn)無須裝備GPS ,且不能通過測量或定位方法獲得其具體的物理位置。1.2問題陳述無線傳感器網(wǎng)絡(luò)覆蓋控制優(yōu)化的主要目的是調(diào)度節(jié)點(diǎn)的休眠間隔時間,滿足覆蓋要求下保持部分節(jié)點(diǎn)為工作狀態(tài),但網(wǎng)絡(luò)仍能提供連續(xù)的檢測服務(wù)。服務(wù)質(zhì)量期望值q (desired QoS 表示了網(wǎng)絡(luò)覆蓋率。為所有工作節(jié)點(diǎn)構(gòu)成的監(jiān)測區(qū)域面積占整個區(qū)域M 面積的比例,即:q =(ki =1SR i M areaM area。假設(shè)在監(jiān)測區(qū)域M 中隨機(jī)均勻部署N 個節(jié)點(diǎn),每

11、個節(jié)點(diǎn)S i (1i N 的監(jiān)測范圍為SR i ,需要從N 個節(jié)點(diǎn)中最少選取多少個工作節(jié)點(diǎn),使得這些工作節(jié)點(diǎn)能夠滿足應(yīng)用期望的服務(wù)質(zhì)量(其中K 是最少選取的工作節(jié)點(diǎn)數(shù)量,即:(ki =1SR i M areaM areaq ,以及如何選取K 個工作節(jié)點(diǎn)。工作節(jié)點(diǎn)的選取應(yīng)考慮節(jié)點(diǎn)的能量大小。由于在每輪中節(jié)點(diǎn)的能量開銷不一致,需要算法保證能量開銷被均勻地分布到每個節(jié)點(diǎn)上,避免某些節(jié)點(diǎn)過早死亡。如果網(wǎng)絡(luò)中的節(jié)點(diǎn)時間不同步也會對覆蓋強(qiáng)度造成影響,假設(shè)節(jié)點(diǎn)時鐘與標(biāo)準(zhǔn)時鐘差在區(qū)間(T /2,T /2上均勻分布,即t U (T /2,T /2,當(dāng)節(jié)點(diǎn)分布滿足Poisson 點(diǎn)過程時,網(wǎng)絡(luò)覆蓋強(qiáng)度8為C n

12、'=C n 2k M exp (M 2k exp (M k exp (M k其中:M 表示區(qū)域M 的面積,表示Poisson 點(diǎn)過程強(qiáng)度。2算法描述2.1工作節(jié)點(diǎn)選取機(jī)制算法中傳感器節(jié)點(diǎn)共有四種狀態(tài):準(zhǔn)備狀態(tài)(ready 、工作狀態(tài)(active 、偵聽狀態(tài)(listening 、休眠狀態(tài)(sleep 。節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換如圖1所示 。在算法每輪開始時,所有節(jié)點(diǎn)都處于準(zhǔn)備狀態(tài)(ready ,首先,從所有節(jié)點(diǎn)中隨機(jī)選取一個根節(jié)點(diǎn)進(jìn)入工作狀態(tài)。首個節(jié)點(diǎn)的隨機(jī)選擇機(jī)制:計算自己此輪中被選中的閾值T (n ,與文獻(xiàn)9選取簇頭的機(jī)制類似,閾值大于事先設(shè)定值則選為工作節(jié)點(diǎn)。T (n =P work1P

13、work Round mod ?1P work E curr E max+Round s div ?1P work1E currE max其中:P work 為被選作工作節(jié)點(diǎn)的概率,即P work =K /N ;Round 為算法運(yùn)行的輪數(shù);Round s 表示節(jié)點(diǎn)連續(xù)沒有被選為工作節(jié)點(diǎn)的輪數(shù),當(dāng)節(jié)點(diǎn)成為工作節(jié)點(diǎn)后,Round s 重置為0。在這個模型中,每一個節(jié)點(diǎn)通過由自身內(nèi)部的晶體振蕩器提供的本地計時器記錄自己的時間。根節(jié)點(diǎn)是所有節(jié)點(diǎn)中選出來的可以作為時間基準(zhǔn)的節(jié)點(diǎn)。這個節(jié)點(diǎn)可以訪問外部時鐘并能夠與物理時鐘達(dá)到同步,根節(jié)點(diǎn)層號為0。同時工作節(jié)點(diǎn)向其鄰居節(jié)點(diǎn)廣播自身信息(self-messa

14、ge ,SM 。SM 信息包括節(jié)點(diǎn)ID 信息、status 和層號。收到SM 信息的節(jié)點(diǎn)檢測與active 節(jié)點(diǎn)之間的距離。若0d Rs ,為了使整個網(wǎng)絡(luò)的能耗均衡,避免個別傳感器節(jié)點(diǎn)提前死亡,傳感器節(jié)點(diǎn)由ready 狀態(tài)以概率P active =P init E current /E max 轉(zhuǎn)為偵聽狀態(tài),成為偵聽節(jié)點(diǎn)。其中,P init 為工作節(jié)點(diǎn)的初始概率。若Rs d 2Rs ,則傳感器節(jié)點(diǎn)由ready 狀態(tài)轉(zhuǎn)為active 狀態(tài)。為了避免在這一輪中有過多的鄰居節(jié)點(diǎn)被選為工作節(jié)點(diǎn),在此引入避讓(back-off 機(jī)制,分別為每個開始節(jié)點(diǎn)設(shè)置一個隨機(jī)時間T d 。若節(jié)點(diǎn)在T d 時間內(nèi)沒有

15、收到其他開始節(jié)點(diǎn)的SM 信息,則將自身狀態(tài)激活為active 狀態(tài),并向其鄰居節(jié)點(diǎn)發(fā)送SM 信息;若在T d 時間內(nèi)又收到其他鄰居節(jié)點(diǎn)的SM 信息,則取消隨機(jī)時間,并再次判斷與此開始節(jié)點(diǎn)的距離。若d Rs 則進(jìn)入listening 狀態(tài);若d Rs 則進(jìn)入active 狀態(tài),并向其鄰居節(jié)點(diǎn)發(fā)送SM 信息。每一個根節(jié)點(diǎn)臨近的鄰居節(jié)點(diǎn)收到SM 信息后,它們就知道父節(jié)點(diǎn)的標(biāo)志符和層號。接著,記錄下標(biāo)志符,給自己設(shè)置一個比父節(jié)點(diǎn)層號大1的層號,然后給根節(jié)點(diǎn)發(fā)送一個反饋信息,表明它們已經(jīng)加入根節(jié)點(diǎn)。同理,其他節(jié)點(diǎn)根據(jù)上述條件決定自身的狀態(tài)和層號,它們鄰近的鄰居將得到SM 信息并加入生成樹。這個過程一直進(jìn)

16、行,直到WSN 中所有的節(jié)點(diǎn)都加入到生成樹為止。然而一個已經(jīng)加入到生成樹的節(jié)點(diǎn)還有可能再一次接收到其他的SM 信息,如果有這種情況,若處于lis-tening 狀態(tài)下的節(jié)點(diǎn)收到SM 信息后,鄰居節(jié)點(diǎn)中工作節(jié)點(diǎn)數(shù)加1,層號信息不變。圖2展示了生成樹的結(jié)果。當(dāng)步驟1結(jié)束時,所有的節(jié)點(diǎn)處于active 或listening 狀態(tài)。Listening 狀態(tài)節(jié)點(diǎn)檢測其d Rs 范圍內(nèi)有無工作節(jié)點(diǎn),若沒有則將自身激活為active 狀態(tài);若Rs 范圍內(nèi)有工作節(jié)點(diǎn),則其工作狀態(tài)不變,等待進(jìn)一步的判斷。直到所有傳感器的感知范圍內(nèi)有一個工作節(jié)點(diǎn)或本身是一個工作節(jié)點(diǎn),層號以及根節(jié)點(diǎn)信息不變。為了滿足網(wǎng)絡(luò)的覆蓋要求

17、,需要進(jìn)一步從listening 節(jié)點(diǎn)中選取節(jié)點(diǎn)進(jìn)入active 狀態(tài)。根據(jù)現(xiàn)有的節(jié)點(diǎn)冗余度數(shù)學(xué)模型10,對節(jié)點(diǎn)分布進(jìn)行進(jìn)一步選取,當(dāng)鄰居節(jié)點(diǎn)數(shù)量大于閾值時,說明節(jié)點(diǎn)為冗余節(jié)點(diǎn),可以關(guān)閉通信設(shè)備,進(jìn)入sleep 狀態(tài);否則節(jié)點(diǎn)成為工作節(jié)點(diǎn),保證網(wǎng)絡(luò)的覆蓋率,閾值的大小與應(yīng)用期望的服務(wù)質(zhì)量q 有關(guān)。為避免多個節(jié)點(diǎn)同時進(jìn)入工作狀態(tài),同理可引入避讓(back-off 機(jī)制。·63·計算機(jī)應(yīng)用研究第29卷當(dāng)整個傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)通過以上算法達(dá)到確定狀態(tài)(進(jìn)入休眠狀態(tài)或工作狀態(tài)之后,將在T w 時間內(nèi)保持整個狀態(tài)不變,經(jīng)過T w 后,所有節(jié)點(diǎn)被重新喚醒,所有傳感器節(jié)點(diǎn)重新在下一輪的鄰

18、居節(jié)點(diǎn)集建立和工作節(jié)點(diǎn)的選取。2.2在生成樹中的廣播時間同步算法在生成樹建立起來后,整個WSN 已經(jīng)被分為幾個可以看到的子樹,如圖3所示 。具有精確外部時鐘的根節(jié)點(diǎn)將同步它的子樹根節(jié)點(diǎn)1、2和3。在1、2、3重置它們的時間為標(biāo)準(zhǔn)時間后,它們會同步其子樹的節(jié)點(diǎn)。這種子樹時鐘同步過程會持續(xù)下去,直到所有節(jié)點(diǎn)設(shè)定與根節(jié)點(diǎn)一樣的時鐘為止。每次的子樹同步過程如圖4所示 。每個節(jié)點(diǎn)時鐘都不相同,因此每兩個節(jié)點(diǎn)間都會有時間偏差,而只有根節(jié)點(diǎn)具有標(biāo)準(zhǔn)的時間。起初根節(jié)點(diǎn)向它的子樹節(jié)點(diǎn)1、2、3廣播一個同步包,假如這個同步包包含節(jié)點(diǎn)1的標(biāo)志符,這意味著根節(jié)點(diǎn)選擇節(jié)點(diǎn)1來進(jìn)行一對同步,因此稱節(jié)點(diǎn)1為消息節(jié)點(diǎn)。假設(shè)根

19、節(jié)點(diǎn)的子節(jié)點(diǎn)會在同一時刻接收到同步信息包。在節(jié)點(diǎn)1接收到同步包后,它知道了包中的標(biāo)志符與它自己的一樣,節(jié)點(diǎn)1記錄接收時間t 2,node1,然后開始處理這個包。在很短的時間后,在節(jié)點(diǎn)1給根節(jié)點(diǎn)發(fā)送返回包之前,記錄瞬時時間t 3,node1,并且把t 2,node1和t 3,node1的信息嵌入到返回包中。當(dāng)根節(jié)點(diǎn)接收到這個信息時也記錄時間t 4。于是根節(jié)點(diǎn)可以計算出與節(jié)點(diǎn)1的時間偏差如下:O R ,node1=(t 2,node1t 1(t 4t 3,node1/2(1其中:O R ,node1表示了時間偏差。最后根節(jié)點(diǎn)再次廣播一個包含與節(jié)點(diǎn)1的偏差和節(jié)點(diǎn)1的時間信息t 2,node 1的包。

20、當(dāng)然節(jié)點(diǎn)1基于偏差O R ,node1就能夠調(diào)整自己的時鐘了。另外的節(jié)點(diǎn)利用這個數(shù)據(jù)包信息也可以知道它們與根節(jié)點(diǎn)的偏差。例如,對于節(jié)點(diǎn)2,有t 2,root +O R ,node1=t 2,node1+O node1,node2(2其中:O node1,node2表示節(jié)點(diǎn)1與2的時間偏差。于是可以得到O R ,node2=O R ,node1(t 2,node1t 2,node2(3因?yàn)楣?jié)點(diǎn)2會接收包括t 2,node1和O R ,node2的廣播包,同時,節(jié)點(diǎn)2也記錄了時間信息t 2,node2,于是O r ,node2可以通過式(3計算得到。在節(jié)點(diǎn)2知道了O R ,Node2后,它將調(diào)整自

21、己的時鐘與根節(jié)點(diǎn)達(dá)到同步。余下的節(jié)點(diǎn)如節(jié)點(diǎn)3可以通過同樣的方式與根節(jié)點(diǎn)達(dá)到同步11。當(dāng)子樹中的所有子節(jié)點(diǎn)都與父節(jié)點(diǎn)同步之后,子樹的同步就實(shí)現(xiàn)了。很明顯,與根節(jié)點(diǎn)同步的節(jié)點(diǎn)1、2和3也可以被看做它們子樹的父節(jié)點(diǎn)。因此,類似的子樹時間同步過程一直進(jìn)行,直到整個WSN 都同步到根節(jié)點(diǎn)。3仿真結(jié)果與評價為了驗(yàn)證該算法選出的工作節(jié)點(diǎn)分布是否良好,在50m 50m 區(qū)域中,隨機(jī)部署100 1000個節(jié)點(diǎn),應(yīng)用服務(wù)期望q =99%,Rs =10m ,Rc =20m 。節(jié)點(diǎn)分布情況如圖5、6中圓點(diǎn)所示,圖中圓盤代表工作節(jié)點(diǎn)的覆蓋范圍。實(shí)驗(yàn)結(jié)果表明,運(yùn)行該算法后,每輪生成的工作節(jié)點(diǎn)在網(wǎng)絡(luò)中分布良好,所選擇的工作

22、節(jié)點(diǎn)完全能夠滿足應(yīng)用服務(wù)期望,而且工作節(jié)點(diǎn)數(shù)相對較少,同時達(dá)到了整個網(wǎng)絡(luò)工作節(jié)點(diǎn)的時間同步,增強(qiáng)了信息的可靠性。圖7為部署500個節(jié)點(diǎn)時對應(yīng)的連通效果,可以清晰地看出,整個工作狀態(tài)的節(jié)點(diǎn)組成的網(wǎng)絡(luò)是連通的,算法保證了在Rc 2Rs 時整個網(wǎng)絡(luò)的連通性。通過在生成樹中廣播時間同步算法,能夠使工作節(jié)點(diǎn)網(wǎng)絡(luò)同步到微秒級,在退避時間T d 的允許范圍,因而也消除了網(wǎng)絡(luò)中時間異步對覆蓋強(qiáng)度的影響。圖8為在50m 50m 監(jiān)測區(qū)域下與OGDC 、PEAS 、GAF 、DELIC 幾種算法所選擇的工作節(jié)點(diǎn)數(shù)的比較。圖中工作節(jié)點(diǎn)數(shù)為每種算法連續(xù)仿真100次后取平均值所得 。由于本文首先選擇出覆蓋冗余較少的節(jié)點(diǎn)

23、作為整個網(wǎng)絡(luò)的支撐節(jié)點(diǎn),然后又引入節(jié)點(diǎn)冗余度數(shù)學(xué)模型選擇節(jié)點(diǎn),使整個網(wǎng)絡(luò)滿足覆蓋要求,所以工作節(jié)點(diǎn)相對較少。從圖中也可以看出,在大多數(shù)情況下DELIC 需要23個工作節(jié)點(diǎn)才能達(dá)到99%以上的覆蓋率,對于GAF 協(xié)議,需要的工作節(jié)點(diǎn)數(shù)量幾乎是該算法的2倍多;PEAS 可以提供與該算法差不多的覆蓋質(zhì)量,但是選出的工作節(jié)點(diǎn)數(shù)量比該算法多50%左右;OGDC 節(jié)點(diǎn)數(shù)最少,覆蓋率相對較低,而且OGDC 需要利用節(jié)點(diǎn)的位置信息來控制工作節(jié)點(diǎn)密度。本文算法無須預(yù)先得知節(jié)點(diǎn)的位置信息,選擇的工作節(jié)點(diǎn)數(shù)目也相對較少,而且隨著部署節(jié)點(diǎn)的增加,工作節(jié)點(diǎn)數(shù)基本不變。(下轉(zhuǎn)第42頁·73·第1期常光

24、強(qiáng),等:基于時間同步的無線傳感器網(wǎng)絡(luò)覆蓋控制優(yōu)化算法了三種模型。運(yùn)用模糊模擬與遺傳算法相結(jié)合,設(shè)計了一種混合智能算法求解所提出的三個模型。最后,通過一個數(shù)值實(shí)驗(yàn)驗(yàn)證了混合智能算法的有效性。表4不同參數(shù)設(shè)定下的求得的-權(quán)值種群規(guī)模模糊模擬次數(shù)P c P m b p-權(quán)值相對誤差/%1003000050160826382301003000070260826392700391003000050110052641110109100300008011205264084009910050000803120826467803241005000070210032647940368100500005046052

25、64691032950300008041203264221015150300007038082642440160參考文獻(xiàn):1BAR-YEHUDA R,EVEN SA local-ratio theorem for approximatingthe weighted vertex cover problemJAnnals of Discrete Mathe-matics,1985,109(25:27-452CHVATAL VA greedy-heuristic for the set cover problemJMathematics of Operations Research,1979,4(

26、3:233-2353DINUR I,SAFRA SThe importance of being biasedC/Proc ofthe34th Annual ACM Symposium on Theory of ComputingNewYork:ACM Press,2002:33-424MONIEN B,SPECKENMEYER ERamsey numbers and an approxi-mation algorithm for the vertex cover problemJActa Informatica, 1985,22(1:115-1235CHLEBIKA M,CHLEBIKOVA

27、 JCrown reductions for the minimumweighted vertex cover problemJDiscrete Applied Mathematics,2008,156(3:292-3126KHOTA S,REGEV OVertex cover might be hard to approximate towithin2-epsilonJJournal of Computer and System Sciences, 2008,74(3:335-3497KARAKOSTAS GA better approximation ratio for the verte

28、x coverproblemJACM Trans on Algorithms,2009,5(4:1-88NI Yao-dongStochastic minimum weight vertex cover problemC/Proc of the5th International Conference on Information and Manage-ment Sciences2006:358-3649ZADEH L AFuzzy setsJInformation and Control,1965,8(3:338-35310KAUFMANN AIntroduction to the theor

29、y of fuzzy subsetsMNewYork:Academic Press,197511NAHMIAS SFuzzy variablesJFuzzy Sets and Systems,1978,1(2:97-11012LIU Bao-dingUncertainty theory:an introduction to its axiomaticfoundationsMBerlin:Springer-Verlag,200413LIU Bao-ding,LIU Y KExpected value of fuzzy variable and fuzzyexpected value models

30、JIEEE Trans on Fuzzy Systems,2002, 10(4:445-45014LIU Bao-ding,IWAMURA KChance constrained programming withfuzzy parametersJFuzzy Sets and Systems,1998,94(2:227-23715HOLLAND JAdaptation in natural and artificial systemMAnnArbor,MI:University of Michigan Press,197516KARP R MReducibility among combinat

31、orial problemsC/Procof Complexity of Computer ComputationNew York:Plenum Press, 1972:85-103(上接第37頁4結(jié)束語本文立足于WSN的覆蓋控制問題提出了一個分布的、高效節(jié)能、與節(jié)點(diǎn)位置無關(guān)、基于時間同步的傳感器網(wǎng)絡(luò)覆蓋算法。在本文算法的工作節(jié)點(diǎn)選取機(jī)制中,節(jié)點(diǎn)通過鄰居節(jié)點(diǎn)的工作狀態(tài)決定自身工作狀態(tài),工作節(jié)點(diǎn)網(wǎng)絡(luò)可達(dá)到時間同步,根據(jù)能量的大小來選擇工作節(jié)點(diǎn)。模擬實(shí)驗(yàn)結(jié)果表明,在無須節(jié)點(diǎn)位置信息的前提下,該算法能夠大大地減少網(wǎng)絡(luò)中的工作節(jié)點(diǎn)數(shù),從而在減少整體能量消耗、均衡節(jié)點(diǎn)能耗方面具有良好的性能。參考文獻(xiàn):1

32、石為人,袁久銀,雷璐寧無線傳感器網(wǎng)絡(luò)覆蓋控制算法研究J自動化學(xué)報,2009,35(5:540-5452REN Yan,ZHANG Si-dong,ZHANG Hong-keTheories and algo-rithms of coverage control for wireless sensor networksJJournal ofSoftware,2006,17(3:422-4333WU Yong-an,LI Min,CAI Zhi-ping,et alA distributed algorithm toapproximate node-weighted minimum a-conne

33、cted(,k-coverage indense sensor networksC/Proc of International Frontiers of Algo-rithmic Workshop2008:221-2324YE Fan,ZHONG G,LU Song-wu,et alPEAS:a robust energy con-serving protocol for long-lived sensor networksC/Proc of the23rdInternational Conference on Distributed Computing Systems2003:28-375ZH