基于能量與功率控制的TopDisc拓?fù)渌惴ㄑ芯?/h1>

2010-03-23 10:17:04于忠平

華東交通大學(xué)學(xué)報(bào)訂閱 2010年3期 收藏

關(guān)鍵詞：發(fā)射功率網(wǎng)絡(luò)拓?fù)?/a>定義

謝 昕，張 恒，于忠平，周 娟

(華東交通大學(xué)信息工程學(xué)院，江西南昌330013)

在無線傳感器網(wǎng)絡(luò)中體系結(jié)構(gòu)，網(wǎng)絡(luò)拓?fù)淇刂芠1-5]具有十分重要的意義。設(shè)計(jì)良好的拓?fù)淇刂平Y(jié)構(gòu)能夠提高路由協(xié)議和MAC協(xié)議的效率，為數(shù)據(jù)融合、時(shí)間同步、目標(biāo)定位等很多方面提供基礎(chǔ)，有利于延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存時(shí)間。

傳感器網(wǎng)絡(luò)中的拓?fù)淇刂瓢凑昭芯糠较蚩梢苑譃閮深?節(jié)點(diǎn)功率控制和層次型拓?fù)淇刂平M織[6-9]。其中，節(jié)點(diǎn)功率控制中的本地平均算法(LMA[10])通過動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的發(fā)射功率來形成拓?fù)浣Y(jié)構(gòu);其主要思想是通過定期廣播一個(gè)包含自己ID的LifeMsg消息，并為鄰居節(jié)點(diǎn)設(shè)置一個(gè)上下限，當(dāng)鄰居數(shù)小于下限時(shí)，就增大發(fā)射功率;當(dāng)大于上限時(shí)，就減弱發(fā)射功率。LMA算法也存在一些問題，它缺少嚴(yán)格的理論推導(dǎo)，在鄰居節(jié)點(diǎn)的判斷條件上沒有嚴(yán)格的說明。層次型拓?fù)淇刂品矫娴腡opDisc[11-12]算法是由Deb等人提出的一種基于圖論中最小支配集問題的經(jīng)典算法。TopDisc算法利用顏色來描述節(jié)點(diǎn)狀態(tài)，解決骨干網(wǎng)拓?fù)浣Y(jié)構(gòu)的形成問題。TopDisc算法中提出兩種節(jié)點(diǎn)標(biāo)記方法，分別為三色算法和四色算法。這兩種方法的區(qū)別在于，四色算法中，節(jié)點(diǎn)多了一種深灰色狀態(tài)的節(jié)點(diǎn)，從而使得兩種算法在形成簇后的結(jié)構(gòu)有所不同。四色算法能形成比三色算法更少的簇，且簇與簇之間的交疊更少;但四色算法相對(duì)于三色算法可能會(huì)形成一些孤獨(dú)的黑色節(jié)點(diǎn)，它不覆蓋灰色節(jié)點(diǎn)。兩種算法的核心思想都是:利用顏色標(biāo)記理論找到簇頭節(jié)點(diǎn);利用與傳輸距離成反比的延時(shí)，使得一個(gè)黑色節(jié)點(diǎn)(簇頭節(jié)點(diǎn))覆蓋更大的范圍。該算法可以在節(jié)點(diǎn)密集的傳感器網(wǎng)絡(luò)中快速的形成分簇結(jié)構(gòu)，并在簇于簇之間建立樹型關(guān)系。但是由于這種算法構(gòu)建成的層次型網(wǎng)絡(luò)的靈活性不強(qiáng)，重復(fù)執(zhí)行算法的開銷過大，且該算法沒有考慮到節(jié)點(diǎn)的剩余能量問題。

本文主要思想是在TopDisc算法的基礎(chǔ)上，通過引入能量、功率控制機(jī)制，動(dòng)態(tài)地改變節(jié)點(diǎn)發(fā)射功率，形成一種不等規(guī)模的簇型結(jié)構(gòu)，減少簇與簇之間的交疊范圍，從而使得簇間工作更加獨(dú)立，減少了簇間的相互干擾。

1 網(wǎng)絡(luò)模型定義

1.1 節(jié)點(diǎn)定義

定義1 所有節(jié)點(diǎn)都有唯一的編號(hào)，即ID信息。

定義2 整個(gè)網(wǎng)絡(luò)中存在一個(gè)sink節(jié)點(diǎn)，該節(jié)點(diǎn)的數(shù)據(jù)處理和通信能力高于其他節(jié)點(diǎn)。有較強(qiáng)的數(shù)據(jù)收集和節(jié)點(diǎn)檢測(cè)、查詢能力，且該節(jié)點(diǎn)有持續(xù)的能源供給，并可以把數(shù)據(jù)傳輸?shù)酵獠烤W(wǎng)絡(luò)。

定義3 假設(shè)節(jié)點(diǎn)能夠知道自己本身的位置，且位置固定。在數(shù)據(jù)傳輸時(shí)，附帶自己的位置信息，使它的鄰居節(jié)點(diǎn)和簇頭節(jié)點(diǎn)都知道它的位置。

定義4 節(jié)點(diǎn)除了進(jìn)行本簇內(nèi)的數(shù)據(jù)收集和數(shù)據(jù)傳輸外，在必要時(shí)候，還必須兼顧簇間數(shù)據(jù)傳輸任務(wù)。

定義5 除sink節(jié)點(diǎn)外，所有節(jié)點(diǎn)的初始能量相同，設(shè)為Emax，傳輸中消耗的能量和所傳輸?shù)淖止?jié)成正比，和傳輸?shù)木嚯x也成正比。耗能公式為E(d)=kαdn

(1)

其中，k為常數(shù)，α代表傳輸?shù)淖止?jié)大小，n滿足關(guān)系2＜n＜4，n的取值與很多因素有關(guān)，如地理情況，信號(hào)干擾等，考慮到這些因素，通常n的取值為3;d代表兩節(jié)點(diǎn)間的距離。

定義6 傳感器節(jié)點(diǎn)具有功率控制能力，假設(shè)節(jié)點(diǎn)的功率控制范圍是[0，F(xiàn)]，F(xiàn)為最大發(fā)射功率，所有節(jié)點(diǎn)開始都在最大發(fā)射功率F下工作，此時(shí)的發(fā)射半徑為R。

定義7 所有節(jié)點(diǎn)都知道自身的當(dāng)前剩余能量，記為:En。在進(jìn)行數(shù)據(jù)傳輸時(shí)，附帶其剩余能量信息，是簇頭節(jié)點(diǎn)知道它的剩余能量。

定義8 給傳感器節(jié)點(diǎn)設(shè)置一個(gè)能量閥值E min，當(dāng)傳感器節(jié)點(diǎn)的能量低于這個(gè)閥值時(shí)，傳感器不能被選為簇頭節(jié)點(diǎn)，但可以傳輸數(shù)據(jù)，直到節(jié)點(diǎn)能量耗盡。

定義9 傳感器節(jié)點(diǎn)狀態(tài)分為5個(gè)狀態(tài)，分別為睡眠、空閑、監(jiān)聽、發(fā)送和接受狀態(tài)。其中規(guī)定睡眠狀態(tài)不消耗能量，其余狀態(tài)在單位時(shí)間內(nèi)都消耗一定的能量。

1.2 網(wǎng)絡(luò)定義

定義1 無線傳感器網(wǎng)絡(luò)可抽象為一個(gè)無向圖G{V，E}，V代表頂點(diǎn)，即無線傳感器節(jié)點(diǎn)的集合;E代表邊，即相鄰節(jié)點(diǎn)之間鏈路的集合?？擅枋鰹?/p>

其中，我們?cè)O(shè)C為所有的簇頭節(jié)點(diǎn)集合，Vi代表節(jié)點(diǎn)i的鄰居信息，i∈C。

定義2 在整個(gè)網(wǎng)絡(luò)的生存期來說，因簇頭的選舉和功率控制機(jī)制導(dǎo)致的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化所消耗的能量，可以忽略不記。

2 基于能量與功率控制的改進(jìn)算法

2.1 簇頭節(jié)點(diǎn)與簇內(nèi)節(jié)點(diǎn)

網(wǎng)絡(luò)起始階段，所有節(jié)點(diǎn)都標(biāo)記為白色節(jié)點(diǎn)，都處于活動(dòng)狀態(tài)，由sink節(jié)點(diǎn)發(fā)起TopDisc算法的三色算法。此階段因?yàn)槭情_始階段，所有節(jié)點(diǎn)的能量都相同，不必考慮能量問題，其過程和三色算法一樣。當(dāng)一個(gè)節(jié)點(diǎn)被選為簇頭節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)記錄下此時(shí)的自身能量信息Enc。三色算法執(zhí)行完之后，所有簇內(nèi)節(jié)點(diǎn)向簇首節(jié)點(diǎn)發(fā)送帶有與簇首節(jié)點(diǎn)距離長(zhǎng)度的消息，消息發(fā)送完成后無任務(wù)的灰色節(jié)點(diǎn)立即進(jìn)入睡眠狀態(tài)，設(shè)定時(shí)間ts1和ts2，并在時(shí)間ts1過后醒來監(jiān)聽簇首節(jié)點(diǎn)消息，并向簇首節(jié)點(diǎn)發(fā)送帶有自身剩余能量的信息，時(shí)間ts2后又進(jìn)入睡眠狀態(tài)，如果在ts2超時(shí)前簇首節(jié)點(diǎn)有消息任務(wù)需要其傳送，立即變?yōu)榛顒?dòng)節(jié)點(diǎn)。當(dāng)簇內(nèi)進(jìn)行簇頭選舉時(shí)，節(jié)點(diǎn)被選舉為簇頭節(jié)點(diǎn)的概率為

其中:l為常數(shù)，En和Emax分別為節(jié)點(diǎn)的當(dāng)前剩余能量和節(jié)點(diǎn)的初始最大能量。

2.2 簇的形成與更新

簇內(nèi)節(jié)點(diǎn)經(jīng)過第一輪三色算法后，形成了網(wǎng)絡(luò)的初始拓?fù)浣Y(jié)構(gòu)(見圖1)。從圖1中可以看出，簇間的交疊范圍比較大，增加了簇間傳遞數(shù)據(jù)沖突的發(fā)生概率，干擾了簇間數(shù)據(jù)的有效傳遞。

為了降低簇間傳遞數(shù)據(jù)發(fā)生沖突的概率，引入了節(jié)點(diǎn)功率控制機(jī)制，動(dòng)態(tài)的調(diào)節(jié)節(jié)點(diǎn)的發(fā)射功率，其主要思想為:因?yàn)榇仡^節(jié)點(diǎn)都知道簇內(nèi)節(jié)點(diǎn)的具體位置，所以簇頭節(jié)點(diǎn)可以通過控制發(fā)射功率的大小來改變自身的發(fā)射半徑，達(dá)到減少簇間交疊范圍的作用。節(jié)點(diǎn)的功率控制范圍是[0，F(xiàn)]。如圖2所示，Dab表示節(jié)點(diǎn)a到節(jié)點(diǎn)b的距離，Dbc表示節(jié)點(diǎn)b到節(jié)點(diǎn)c的距離，因?yàn)镈ab＞Dbc，所以我們選擇調(diào)節(jié)節(jié)點(diǎn)c的發(fā)射功率，發(fā)射功率調(diào)節(jié)滿足下面公式

其中:m為常數(shù)，m的取值在[0，1]之間，取值根據(jù)實(shí)際情況而定;R為最大發(fā)射半徑。圖3為圖2經(jīng)過功率控制機(jī)制后的更新圖。

從圖3可以看出，簇間的交疊減少，他們之間包含的灰色節(jié)點(diǎn)也相應(yīng)的減少。通過節(jié)點(diǎn)功率控制機(jī)制，我們得到圖1更新后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如圖4。

從圖4可以看出，簇間的交疊和簇間包含的灰色節(jié)點(diǎn)減少的更加明顯，從而大大降低了簇間通信發(fā)生沖突的概率。

2.3 簇的維護(hù)

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)穩(wěn)定之后，為確保簇間通信有效的維持下去，還要對(duì)拓?fù)浣Y(jié)構(gòu)進(jìn)行維護(hù)，起維護(hù)過程包括兩個(gè)方面。

第一:當(dāng)簇頭節(jié)點(diǎn)的當(dāng)前能量滿足(6)式時(shí)，要選擇新的簇頭節(jié)點(diǎn)。其中:En代表節(jié)點(diǎn)的當(dāng)前剩余能量;Enc代表節(jié)點(diǎn)被選為簇頭時(shí)，記錄下來的能量。

圖1 網(wǎng)絡(luò)初始拓?fù)浣Y(jié)構(gòu)

圖2 無功率機(jī)制

圖3 通過功率機(jī)制

圖4 更新后網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

第二:新的簇頭節(jié)點(diǎn)的選擇需要滿足時(shí)延機(jī)制。時(shí)延機(jī)制可表示為(7)式，其中:C1和C2代表常數(shù);dy表示該節(jié)點(diǎn)到當(dāng)前簇頭節(jié)點(diǎn)的距離;Ey表示該節(jié)點(diǎn)當(dāng)前自身的剩余能量。

通過時(shí)延機(jī)制選出新的簇頭節(jié)點(diǎn)，并通過功率控制機(jī)制，更新網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，最終回到網(wǎng)絡(luò)拓?fù)浞€(wěn)定階段。

3 算法仿真及結(jié)果分析

本文用MATLAB作為仿真平臺(tái)，在200m×200m的區(qū)域內(nèi)，隨機(jī)地散布了200個(gè)傳感器節(jié)點(diǎn)，規(guī)定每個(gè)傳感器初始能量都為1。在工作半小時(shí)后，隨機(jī)地抽取其中100個(gè)節(jié)點(diǎn)，并記錄下剩余能量值。圖5為兩種算法剩余能量的比較圖，從圖5中可以看出，改進(jìn)后算法的能量分布更加的均勻，原因是節(jié)點(diǎn)被輪流選為簇頭節(jié)點(diǎn)。TopDisc算法沒有考慮到節(jié)點(diǎn)的剩余能量問題，所以出現(xiàn)了部分節(jié)點(diǎn)死亡;改進(jìn)后算法的節(jié)點(diǎn)剩余能量遠(yuǎn)遠(yuǎn)大于原TopDisc算法，主要原因是通過了功率控制機(jī)制，間接地降低了節(jié)點(diǎn)的發(fā)射功率大小，節(jié)省了節(jié)點(diǎn)的多余能量開銷。

圖5 改進(jìn)后算法與原TopDisc算法剩余能量比較

圖6 改進(jìn)后算法與原TopDisc算法生命周期比較

圖6為兩種算法的生命周期的比較，改進(jìn)后算法因?yàn)楣?jié)點(diǎn)輪流的來做簇頭節(jié)點(diǎn)，且通過功率控制機(jī)制對(duì)節(jié)點(diǎn)的發(fā)射功率進(jìn)行控制，生命周期有顯著地提高，直到2 000秒才出現(xiàn)死亡節(jié)點(diǎn);相對(duì)于原TopDisc算法，沒有出現(xiàn)在同一時(shí)刻，節(jié)點(diǎn)的急劇死亡，節(jié)點(diǎn)數(shù)量的變化比較平穩(wěn);而原TopDisc算法，隨著時(shí)間的推移，節(jié)點(diǎn)死亡的速度也加快。

4 結(jié)束語

本文在TopDisc三色算法基礎(chǔ)上，提出一種基于能量與功率控制的拓?fù)渌惴?。通過實(shí)驗(yàn)仿真發(fā)現(xiàn)，改進(jìn)后的算法在節(jié)點(diǎn)能耗的控制上，具有明顯的效果，減少了簇間的交疊范圍，使得簇間通信更加獨(dú)立，降低了簇間通信發(fā)生沖突的概率，提高了整個(gè)網(wǎng)絡(luò)的生命周期。本文側(cè)重于改進(jìn)算法的理論研究，但在實(shí)際應(yīng)用中可能還會(huì)遇到很多的問題，下一步的研究重點(diǎn)將放到實(shí)際應(yīng)用中，從而完善算法在實(shí)際應(yīng)用的不足。

[1] 張學(xué)，陸桑璐，陳貴海，等.無線傳感器網(wǎng)絡(luò)的拓?fù)淇刂芠J].軟件學(xué)報(bào)，2007，18(4):943-954.

[2] 楊賀，張樹東，孫利民.無線傳感器網(wǎng)絡(luò)的拓?fù)淇刂芠J].計(jì)算機(jī)科學(xué)，2007，34(1):36-38.

[3] LIL，HALPERN JY，BAHL P.Analysis of a cone-based distributed topology control algorithm forwirelessmu lti-hop networks[C].In:Proc ACM Sym p on Principles of Distributed Computing(PODC)，Acm，Newport，RI，2001:264-273.

[4] AMISA D，PRAKASH R，VUONGTHP.MaxMin d-cluster formation inwirelessad hoc Networks[C].In:Proc IEEEConfon Computer Communications(INFOCOM)，IEEE.1999:32-41.

[5] 孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社，2005.

[6] 陳力軍，毛鶯池，陳道蓄，等.平均度約束的無線傳感器網(wǎng)絡(luò)拓?fù)淇刂芠J].計(jì)算機(jī)學(xué)報(bào)，2007，30(9):1 044-1 050.

[7] WEIY，HEIDEMANN J，ESTRIN D.An energy-efficientMAC protocol forwireless sensornetworks[J].Scientific Research Publishing，2008(1):59-69.

[8] 唐小軍，曹長(zhǎng)修，譚燕.無線傳感器網(wǎng)絡(luò)基于能量效率的分布式拓?fù)淇刂芠J].計(jì)算機(jī)應(yīng)用，2007，27(6):207-209.

[9] ZHU J，ZHAOH，XU JQ.An energy balanced reliable routingmetric in WSNs[J].Scientific Research Publishing，2009(1):22-26.

[10] KUBISCH M，KARLH，WOLISZ A.Distributed algorithms for transmission power controlinwireless sensornetworks[C].IEEEWCNC 2003，New Orleans，Louisiana，IEEE，2003:16-20.

[11] DEB B，BHATNAGARS，NATH B.A topology discovery algorithm for sensor networkswith applications to network management[J].DCSTechnical Report DCS-TR-411，Rutgers University，2001(5):26-30.

[12] CHANDRA R，F(xiàn)ETZERC，HOGSTEDTK.Adaptive topology discovery in hybridwireless networks[C].Proceedingsin Informatics，1st International Conference on Ad-hoc Networks andWireless，Toronto，2002:356-359.

猜你喜歡

發(fā)射功率網(wǎng)絡(luò)拓?fù)?/a>定義

無線電波發(fā)射功率防爆要求與檢測(cè)方法

工礦自動(dòng)化(2024年6期)2024-08-22 00:00:00

基于通聯(lián)關(guān)系的通信網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法

網(wǎng)絡(luò)安全與數(shù)據(jù)管理(2022年2期)2022-05-23 13:25:46

電子制作(2018年23期)2018-12-26 01:01:16

放大轉(zhuǎn)發(fā)中繼器降低發(fā)射功率的選擇策略研究

無線互聯(lián)科技(2017年24期)2018-01-22 10:39:24

淺談AC在WLAN系統(tǒng)中的應(yīng)用

中國管理信息化(2017年18期)2018-01-04 18:41:52

勞斯萊斯古斯特與魅影網(wǎng)絡(luò)拓?fù)鋱D

汽車維修技師(2017年10期)2017-03-17 02:25:01

基于功率分配最優(yōu)中繼選擇的研究

物聯(lián)網(wǎng)技術(shù)(2017年2期)2017-03-15 17:18:11

電測(cè)與儀表(2016年5期)2016-04-22 01:13:46

成功的定義

山東青年(2016年1期)2016-02-28 14:25:25

修辭學(xué)的重大定義

當(dāng)代修辭學(xué)(2014年3期)2014-01-21 02:30:44