無線傳感器網(wǎng)絡(luò)時(shí)間同步與成簇算法

1、無線傳感器網(wǎng)絡(luò)時(shí)間同步與成簇算法    0引言融合了傳感器技術(shù)、信息處理技術(shù)和網(wǎng)絡(luò)通信技術(shù)的無線傳感器網(wǎng)絡(luò)(wirelesssensornetworks，WSNs)由分布在物理空間上大量傳感器節(jié)點(diǎn)通過自組織的方式構(gòu)建網(wǎng)絡(luò)，節(jié)點(diǎn)通過集成各種微型傳感器來感知環(huán)境或監(jiān)測對(duì)象信息，協(xié)作地處理感知信息，并以自組織多跳無線通信方式將信息傳送到用戶，從而實(shí)現(xiàn)隨時(shí)獲取感興趣區(qū)域信息。WSNs在軍事、工業(yè)、農(nóng)業(yè)、醫(yī)療及環(huán)境監(jiān)測等領(lǐng)域有廣泛的應(yīng)用前景，在我國"國家中長期科學(xué)和技術(shù)發(fā)展0引 言融合了傳感器技術(shù)、信息處理技術(shù)和網(wǎng)絡(luò)通信技術(shù)的無線傳感器網(wǎng)絡(luò)(wirele

2、ss sensor networks，WSNs)由分布在物理空間上大量傳感器節(jié)點(diǎn)通過自組織的方式構(gòu)建網(wǎng)絡(luò)，節(jié)點(diǎn)通過集成各種微型傳感器來感知環(huán)境或監(jiān)測對(duì)象信息，協(xié)作地處理感知信息，并以自組織多跳無線通信方式將信息傳送到用戶，從而實(shí)現(xiàn)隨時(shí)獲取感興趣區(qū)域信息。WSNs在軍事、工業(yè)、農(nóng)業(yè)、醫(yī)療及環(huán)境監(jiān)測等領(lǐng)域有廣泛的應(yīng)用前景，在我國"國家中長期科學(xué)和技術(shù)發(fā)展規(guī)劃綱要"重點(diǎn)領(lǐng)域中，"傳感器網(wǎng)絡(luò)和智能信息處理"被列為"信息產(chǎn)業(yè)"中七個(gè)主題之一。時(shí)間同步是WSNs應(yīng)用的重要組成部分，控制消息沖突、數(shù)據(jù)融合、節(jié)點(diǎn)定位等方面都要求節(jié)點(diǎn)間保持同步。在保持

3、節(jié)點(diǎn)時(shí)間同步的基礎(chǔ)上，獲取節(jié)點(diǎn)的鄰居信息，根據(jù)鄰居信息，對(duì)全網(wǎng)節(jié)點(diǎn)進(jìn)行自組織成簇，在簇內(nèi)進(jìn)行數(shù)據(jù)融合，減少網(wǎng)絡(luò)的數(shù)據(jù)流量，以延長網(wǎng)絡(luò)的壽命。     1相關(guān)研究工作文獻(xiàn)1通過動(dòng)態(tài)選舉簇頭來平均網(wǎng)絡(luò)節(jié)點(diǎn)能耗，其他節(jié)點(diǎn)根據(jù)簇頭信號(hào)的強(qiáng)度來作為判斷是否加入該簇的依據(jù)；文獻(xiàn)2在文獻(xiàn)1的基礎(chǔ)上進(jìn)行了改進(jìn)，通過設(shè)立軟、硬門限進(jìn)一步降低了能耗，只有當(dāng)節(jié)點(diǎn)感知數(shù)據(jù)或其增幅超過預(yù)先設(shè)定的閾值時(shí)，節(jié)點(diǎn)才發(fā)送數(shù)據(jù)；文獻(xiàn)3提出了一種隨機(jī)簇組織局部算法，并在此基礎(chǔ)上，提出了建立層次化簇結(jié)構(gòu)的思想；文獻(xiàn)4提出的簇組織算法，使各簇作用域無重疊且大小基本相等，并且，在舊節(jié)點(diǎn)失效和新節(jié)點(diǎn)

4、加入時(shí)，簇具有一定程度的自愈能力；文獻(xiàn)5提出了一種基于時(shí)間觸發(fā)的簇組織算法，僅當(dāng)特定事件發(fā)生時(shí)，才啟動(dòng)簇組織過程，簇成員同簇頭之間，允許多跳通信；文獻(xiàn)6著重解決簇組織完畢后，相鄰簇之間的連通和簇問路由建立問題，在成簇以后，簇頭和簇頭之間借助非簇頭節(jié)點(diǎn)進(jìn)行通信。但是，上述的算法中沒有考慮成簇消息發(fā)送過程中的沖突問題，簇頭間借助中間節(jié)點(diǎn)通信將帶來很多的交換消息，且問題過于復(fù)雜。本文在提出一種時(shí)間同步算法的基礎(chǔ)上，利用時(shí)隙劃分，有效地克服成簇消息傳輸過程中的沖突問題；再基于節(jié)點(diǎn)的度、節(jié)點(diǎn)的剩余能量等參數(shù)加權(quán)選取簇頭。成簇以后，通過動(dòng)態(tài)改變簇頭節(jié)點(diǎn)的通信功率和通信頻率，以實(shí)現(xiàn)簇頭間一跳通信，且其他的節(jié)

5、點(diǎn)不會(huì)串聽簇頭問的通信，有效降低節(jié)點(diǎn)的能耗。     2時(shí)間同步過程描述同步機(jī)制采用CS模式，由傳感器網(wǎng)絡(luò)中的Sink節(jié)點(diǎn)以多跳方式周期性地廣播時(shí)間同步消息，所有節(jié)點(diǎn)在收到該同步消息后，充分考慮可能造成消息傳輸延時(shí)的原因，對(duì)消息中攜帶的時(shí)間進(jìn)行糾正，然后，將糾正結(jié)果作為本地時(shí)間，同時(shí)記錄收到消息的同步序列號(hào)，如果再次收到相同序列號(hào)的消息，則直接丟棄不做處理。2.1 同步消息擴(kuò)散過程中的偏移量在WSNs中，將消息在節(jié)點(diǎn)間傳遞的過程分為如下6個(gè)部分：1)發(fā)送節(jié)點(diǎn)構(gòu)造一條消息所需要的時(shí)間，包括內(nèi)核協(xié)議處理和緩沖時(shí)間等，設(shè)為tsend；2)消息等待傳輸信道空閑所

6、需時(shí)間，即從等待信道空閑到消息開始發(fā)送時(shí)的延遲，設(shè)為taccess；3)發(fā)送節(jié)點(diǎn)按位(bit)發(fā)射消息需時(shí)間，該時(shí)間取決于消息長度和發(fā)射速率，設(shè)為ttrans；4)消息在2個(gè)節(jié)點(diǎn)之間傳輸介質(zhì)中的傳播時(shí)間，設(shè)為tprop；5)接收節(jié)點(diǎn)按位(bit)接收消息并傳遞給MAC層的時(shí)間，設(shè)為treccp；6)接收節(jié)點(diǎn)重新組裝消息并傳遞給上層應(yīng)用所需的時(shí)間，設(shè)為treceive。從發(fā)送節(jié)點(diǎn)生成同步消息到接收節(jié)點(diǎn)接收到同步消息，總的用時(shí)t如公式(1)所示在實(shí)際的應(yīng)用中，可以根據(jù)所采用的無線傳感器節(jié)點(diǎn)的型號(hào)，計(jì)算同步消息擴(kuò)散過程中的時(shí)間偏移量，以有效地進(jìn)行時(shí)間偏移糾正。2.2 同步消息擴(kuò)散過程中的沖突避免機(jī)制

7、在網(wǎng)絡(luò)初始化時(shí)，Sink節(jié)點(diǎn)廣播時(shí)間同步消息，所有節(jié)點(diǎn)在收到同步消息后，對(duì)該消息中的時(shí)間域進(jìn)行偏移量糾正，將糾正后的時(shí)間作為節(jié)點(diǎn)的本地時(shí)間，但是，并不立即轉(zhuǎn)發(fā)，而是隨機(jī)延時(shí)一段時(shí)間，以避免因多個(gè)節(jié)點(diǎn)同時(shí)轉(zhuǎn)發(fā)該消息而造成再次沖突，隨機(jī)延時(shí)后根據(jù)信號(hào)強(qiáng)度指示器RSSI的值判斷節(jié)點(diǎn)信道是否空閑。如果信道空閑，節(jié)點(diǎn)將轉(zhuǎn)發(fā)糾正后的同步時(shí)間，當(dāng)所有節(jié)點(diǎn)僅轉(zhuǎn)發(fā)一次時(shí)間同步消息時(shí)，全網(wǎng)節(jié)點(diǎn)將保持時(shí)間同步?；贜esC語言定義的時(shí)間同步消息格式如下所示：2.3 同步時(shí)間更新周期由于不同節(jié)點(diǎn)的時(shí)間晶振頻率存在細(xì)微差異，在上次節(jié)點(diǎn)時(shí)間同步的基礎(chǔ)上，經(jīng)過一段時(shí)間后，不同節(jié)點(diǎn)的本地時(shí)間又會(huì)出現(xiàn)新的偏差，當(dāng)這種偏差超出協(xié)

8、議要求的時(shí)間同步精度時(shí)，需要重新對(duì)全網(wǎng)節(jié)點(diǎn)進(jìn)行時(shí)間同步，時(shí)間同步的更新周期的推導(dǎo)公式如下f+=f(1+)，式中，f為節(jié)點(diǎn)的基準(zhǔn)晶振頻率；為晶振誤差率系數(shù)；f+為全網(wǎng)節(jié)點(diǎn)中最大頻率，最小頻率為f_，則f_=f(1-)；T為所有節(jié)點(diǎn)間的最大周期差，則設(shè)T為時(shí)間同步更新的周期，當(dāng)t為所要求時(shí)間同步精度時(shí)如式(2)所示，在已知晶振誤差率和同步精度的前提下，能計(jì)算節(jié)點(diǎn)時(shí)間同步的更新周期。3成簇算法在全網(wǎng)時(shí)間同步后，對(duì)全網(wǎng)進(jìn)行成簇。為了使研究更具有針對(duì)性，同時(shí)，使解決的問題更加突出，本文設(shè)WSNs中的節(jié)點(diǎn)隨機(jī)部署，部署后節(jié)點(diǎn)不可移動(dòng)，每個(gè)節(jié)點(diǎn)有全局唯一的ID標(biāo)識(shí)，全網(wǎng)的ID標(biāo)識(shí)是連續(xù)遞增的，節(jié)點(diǎn)的部署密度

9、夠保證全網(wǎng)的可靠連通，每個(gè)節(jié)點(diǎn)能夠?qū)崟r(shí)讀取自身的剩余能量。3.1 鄰居節(jié)點(diǎn)信息獲取過程設(shè)計(jì)2個(gè)交換消息完成此階段：Energy(u)消息用來交換節(jié)點(diǎn)的ID標(biāo)識(shí)、節(jié)點(diǎn)的剩余能量以及節(jié)點(diǎn)可能的鄰居個(gè)數(shù)；Degree(u)消息用來交換節(jié)點(diǎn)的度(即是該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的數(shù)目)。Energy(u)的消息格式為：鄰居節(jié)點(diǎn)信息獲取過程如下：1)為了避免在鄰居節(jié)點(diǎn)信息的交換過程中消息的傳輸發(fā)生沖突，在完成時(shí)間同步后，為每個(gè)節(jié)點(diǎn)分配一個(gè)時(shí)隙t，根據(jù)ID標(biāo)識(shí)由小到大，每個(gè)節(jié)點(diǎn)只在自己的時(shí)隙廣播消息；2)節(jié)點(diǎn)在自己的時(shí)隙廣播一次Energy(u)消息，在一跳通信范圍之內(nèi)的鄰居節(jié)點(diǎn)接收到該消息后，保存該消息中所攜帶的源

10、節(jié)點(diǎn)ID和源節(jié)點(diǎn)的剩余能量。在所有節(jié)點(diǎn)都廣播了一次Energy(u)消息后，全網(wǎng)內(nèi)的節(jié)點(diǎn)均知道自己鄰居節(jié)點(diǎn)的ID及節(jié)點(diǎn)的剩余能量。3)為了進(jìn)一步獲取鄰居節(jié)點(diǎn)的度，必須進(jìn)行二次信息交換。每個(gè)節(jié)點(diǎn)分別在自己的時(shí)隙廣播Degree(u)消息，在一跳通信范圍之內(nèi)的鄰居節(jié)點(diǎn)接收到該消息后，保存該消息中所攜帶的源節(jié)點(diǎn)的度。在所有節(jié)點(diǎn)都廣播了一次Degree(u)消息后，全網(wǎng)內(nèi)的節(jié)點(diǎn)均準(zhǔn)確地獲取到鄰居節(jié)點(diǎn)的信息，該信息包括鄰居節(jié)點(diǎn)的度、鄰居節(jié)點(diǎn)ID以及鄰居節(jié)點(diǎn)剩余能量，然后，該節(jié)點(diǎn)根據(jù)鄰居節(jié)點(diǎn)度和剩余能量得到鄰居節(jié)點(diǎn)的權(quán)值。進(jìn)行二次控制信息交換的主要優(yōu)點(diǎn)是得到的鄰居表中包含的信息比較全面，為下一步簇頭的選取

11、及骨干網(wǎng)的建立提供了較好的先決條件；缺點(diǎn)是每一次獲取鄰居表的等待時(shí)間可能會(huì)比較長，但是，由于鄰居表獲取時(shí)交換的消息短，這樣，每次消息發(fā)送所耗費(fèi)的時(shí)間和能量均比較小，在分配時(shí)隙一定的情況下，可以初步對(duì)全網(wǎng)的性能做出評(píng)價(jià)。     3.2成簇過程描述在簇頭的選取過程中，每個(gè)節(jié)點(diǎn)比較其自身節(jié)點(diǎn)的權(quán)值與其鄰居節(jié)點(diǎn)的權(quán)值的大小，如果節(jié)點(diǎn)發(fā)現(xiàn)有鄰居節(jié)點(diǎn)的權(quán)值大于其自身的權(quán)值時(shí)，那么，它將等待其他節(jié)點(diǎn)成為簇頭的消息；反之，它將宣布自己成為簇頭，并且，廣播自己已經(jīng)成為了簇頭的消息，它的鄰居節(jié)點(diǎn)在接收到消息以后，記住自己所在簇的簇頭，且在這個(gè)周期內(nèi)不再競爭簇頭。為了進(jìn)一步減少網(wǎng)絡(luò)通信的數(shù)據(jù)量，當(dāng)節(jié)點(diǎn)已經(jīng)成為某個(gè)簇的成員后，它將不會(huì)再次成為其它簇的成員。如圖1所示，設(shè)全網(wǎng)