無(wú)線(xiàn)傳感器網(wǎng)絡(luò)數(shù)據(jù)聚集調(diào)度技術(shù)的研究.pdf

1、隨著傳感器技術(shù)、嵌入式計(jì)算技術(shù)以及無(wú)線(xiàn)通信技術(shù)的迅速發(fā)展,無(wú)線(xiàn)傳感器網(wǎng)絡(luò)以其低成本、自組織網(wǎng)絡(luò)的優(yōu)點(diǎn)被廣泛地應(yīng)用在環(huán)境監(jiān)測(cè)、醫(yī)療衛(wèi)生、國(guó)防軍事等眾多領(lǐng)域。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)作為一種全新的信息獲取和處理技術(shù),對(duì)網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)收集到的感知數(shù)據(jù)進(jìn)行操作是必不可少的,其中數(shù)據(jù)聚集就是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)上一項(xiàng)最基本的操作,近年來(lái)受到學(xué)術(shù)界的廣泛關(guān)注。在很多無(wú)線(xiàn)傳感器網(wǎng)絡(luò)應(yīng)用中,管理員或用戶(hù)通常需要通過(guò)基站提出一些關(guān)于感知區(qū)域中某些物理屬性的聚集查詢(xún),此

2、時(shí)基站需要將網(wǎng)絡(luò)中所有或部分傳感器節(jié)點(diǎn)獲取的感知數(shù)據(jù)進(jìn)行聚集,并將聚集值返回給查詢(xún)者。為了消除聚集過(guò)程中無(wú)線(xiàn)通信帶來(lái)的干擾,需要為網(wǎng)絡(luò)生成一個(gè)無(wú)沖突的聚集調(diào)度,并最小化聚集時(shí)間,該問(wèn)題稱(chēng)為聚集調(diào)度問(wèn)題。因此,聚集調(diào)度方法滿(mǎn)足了查詢(xún)者希望迅速獲得聚集結(jié)果的需求。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)由一組低成本、低功耗的無(wú)線(xiàn)傳感器節(jié)點(diǎn)通過(guò)自組織方式形成網(wǎng)絡(luò),具有節(jié)點(diǎn)能量有限、節(jié)點(diǎn)通信能力有限、網(wǎng)絡(luò)動(dòng)態(tài)變化等特點(diǎn)。這些給無(wú)線(xiàn)傳感器網(wǎng)絡(luò)上聚集調(diào)度問(wèn)題的研究帶來(lái)了很多

3、挑戰(zhàn),包括如何設(shè)計(jì)能量有效的聚集調(diào)度算法、如何設(shè)計(jì)適用于動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)涞恼{(diào)度算法、如何提高算法的數(shù)據(jù)傳輸率等。針對(duì)上述挑戰(zhàn),本文從多方面考慮了無(wú)線(xiàn)傳感器網(wǎng)絡(luò)上的聚集調(diào)度問(wèn)題,并提出相應(yīng)的策略和算法。本文的研究工作及成果包括以下幾個(gè)方面。
　　首先,本文提出了無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的分布式聚集調(diào)度算法?，F(xiàn)有的聚集調(diào)度算法均為集中式算法,不適用于動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)?且聚集時(shí)間延遲較高。針對(duì)上述問(wèn)題,本文提出了一種兩階段的分布式聚集調(diào)度算法。第一

4、階段利用極大獨(dú)立集的方法,分布式地構(gòu)造一棵具有良好性質(zhì)的聚集樹(shù),并將網(wǎng)絡(luò)中的節(jié)點(diǎn)分為不同的角色。在第二階段網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)首先通過(guò)相互通信得到局部的拓?fù)湫畔?然后根據(jù)獲取的信息分布式地完成調(diào)度生成。由于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的聚集調(diào)度問(wèn)題已被證明為NP-難問(wèn)題,本文給出的分布式聚集調(diào)度算法為一個(gè)近似算法,通過(guò)理論分析得出該算法的近似比接近于常數(shù),改進(jìn)了原有算法的聚集時(shí)間上界。本文針對(duì)動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)溥M(jìn)一步提出了一種自適應(yīng)的分布式聚集調(diào)度算法

5、,包括自適應(yīng)的聚集樹(shù)結(jié)構(gòu)維護(hù)和自適應(yīng)的聚集調(diào)度更新。
　　第二,本文針對(duì)多基站無(wú)線(xiàn)傳感器網(wǎng)絡(luò)提出了兩種聚集調(diào)度算法。單基站無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中存在節(jié)點(diǎn)負(fù)載不平衡與能量消耗不平衡的問(wèn)題,而在網(wǎng)絡(luò)中布置多個(gè)計(jì)算和通信能力強(qiáng)大的基站可以有效地緩解該問(wèn)題,因此多基站無(wú)線(xiàn)傳感器網(wǎng)絡(luò)也被廣泛關(guān)注與應(yīng)用。本文提出了適用于該類(lèi)型網(wǎng)絡(luò)的兩種聚集調(diào)度算法,兩算法均分為三個(gè)階段,第一階段為網(wǎng)絡(luò)構(gòu)造出一個(gè)聚集森林作為通信骨干網(wǎng),第二階段和第三階段對(duì)聚集森林中

6、的所有節(jié)點(diǎn)以自底向上的方式逐層生成聚集調(diào)度。第一個(gè)調(diào)度算法采用維諾圖劃分的方法構(gòu)造聚集森林,而第二個(gè)調(diào)度算法采用網(wǎng)絡(luò)支配集的思想構(gòu)造出一個(gè)具有良好性質(zhì)的聚集森林,從而改進(jìn)了第一個(gè)算法。本文通過(guò)理論分析給出了兩算法聚集時(shí)間的上界,并證明第二個(gè)算法性能優(yōu)于第一個(gè)算法。模擬實(shí)驗(yàn)驗(yàn)證了兩算法的有效性。
　　第三,本文提出了適用于周期輪轉(zhuǎn)模式無(wú)線(xiàn)傳感器網(wǎng)絡(luò)上的聚集調(diào)度算法。針對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量有限的特點(diǎn),周期輪轉(zhuǎn)的節(jié)點(diǎn)工作模式逐漸被采

7、用,即節(jié)點(diǎn)在每個(gè)工作周期中工作一段時(shí)間,在其余的時(shí)間進(jìn)行睡眠。周期輪轉(zhuǎn)模式可以很大程度上節(jié)省傳感器節(jié)點(diǎn)的能量,從而延長(zhǎng)網(wǎng)絡(luò)的生命周期,具有廣泛的應(yīng)用前景。本文考慮了該類(lèi)型的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)上的聚集調(diào)度問(wèn)題,并提出一種聚集調(diào)度算法來(lái)解決該問(wèn)題。該算法首先構(gòu)造出網(wǎng)絡(luò)的一個(gè)分層結(jié)構(gòu),然后根據(jù)該結(jié)構(gòu)進(jìn)行工作周期調(diào)度。理論分析得出該算法的近似比接近于常數(shù),模擬實(shí)驗(yàn)也驗(yàn)證了該算法的有效性。
　　第四,本文為無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的聚集調(diào)度提出了一種新的

8、機(jī)會(huì)聚集調(diào)度機(jī)制。已有聚集調(diào)度算法未考慮聚集過(guò)程中可能發(fā)生的傳輸失敗,因此很難適用于鏈路質(zhì)量不理想的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)。針對(duì)此問(wèn)題,本文利用機(jī)會(huì)路由的思想提出了一種兩階段的機(jī)會(huì)聚集調(diào)度機(jī)制,以提高已有調(diào)度算法的數(shù)據(jù)傳輸率。該機(jī)制可以應(yīng)用在任一聚集調(diào)度算法之上,是對(duì)已有聚集調(diào)度算法工作的一個(gè)有力補(bǔ)充。機(jī)會(huì)聚集調(diào)度機(jī)制在第一階段為已有調(diào)度進(jìn)行機(jī)會(huì)鏈路擴(kuò)展,即為網(wǎng)絡(luò)添加一些質(zhì)量較好的機(jī)會(huì)鏈路,并提出了兩種鏈路選擇策略。該機(jī)制在第二階段依照擴(kuò)展后的