《拓?fù)浣Y(jié)構(gòu)控制》

1、拓?fù)浣Y(jié)構(gòu)控制 概述 n 在傳感器網(wǎng)絡(luò)中 , 傳感器節(jié) 點(diǎn) 是體 積微 小的 嵌 入 式 設(shè)備 , 采 用能量有限的電池供電 , 它的計(jì)算 能力 和通 信能 力十分有限 , 所 以除了要設(shè)計(jì)能 量高效的 MAC 協(xié) 議、 l路由協(xié)議以及應(yīng)用層協(xié)議 之外 , 還 要設(shè)計(jì)優(yōu)化的網(wǎng)絡(luò)拓?fù)淇刂茩C(jī)制。對(duì)于 自組織的無線傳感器網(wǎng)絡(luò)而言 ,網(wǎng)絡(luò)拓?fù)淇刂茖?duì)網(wǎng) 絡(luò)性能影響很大。良好的拓?fù)浣Y(jié)構(gòu)能夠提高路由 協(xié)議和 MAC 協(xié)議的效率 , 為數(shù) 據(jù)融 合、時(shí)間同 步 和目 標(biāo) 定位 等 很多方面提供基礎(chǔ) , 有利于延 長(zhǎng) 整個(gè) 網(wǎng)絡(luò) 的生 存 時(shí)間。所 以 , 拓 撲控 制是 傳感器網(wǎng)絡(luò)中的一個(gè)基本問題。 網(wǎng)絡(luò)的拓?fù)?/p>

2、結(jié)構(gòu)控制與優(yōu)化意義 n( 1) 影響整個(gè)網(wǎng) 絡(luò)的 生存 時(shí)間 n( 2) 減小節(jié)點(diǎn)間通信干擾 , 提高網(wǎng)絡(luò)通信效率。 n( 3) 為路由協(xié)議提供基礎(chǔ)。 n( 4) 影響數(shù)據(jù)融合。 n( 5) 彌補(bǔ)節(jié)點(diǎn)失效的影響。 拓?fù)淇刂浦饕?究的問 題 n在 滿足網(wǎng) 絡(luò)覆 蓋度和 連通 度的 前 提下 , 通過功率控制 和骨干網(wǎng)節(jié)點(diǎn)選擇 , 剔除節(jié)點(diǎn)之間不必要的通信鏈路 , 形 成一個(gè)數(shù)據(jù)轉(zhuǎn)發(fā)的優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)。具體地講 , 傳感器網(wǎng)絡(luò) 中的 拓?fù)淇?制按 照研 究方向 可以 分為兩 類 : 節(jié)點(diǎn)功率 控制和層次型拓?fù)浣Y(jié)構(gòu)組織 。功率控制機(jī)制調(diào)節(jié)網(wǎng)絡(luò)中 每個(gè)節(jié)點(diǎn)的發(fā)射功 率 , 在滿足網(wǎng)絡(luò)連通度的前提下 ,

3、均衡 節(jié)點(diǎn)的單跳可達(dá)鄰居數(shù)目。層次型拓?fù)淇刂评梅执貦C(jī) 制 ,讓一些節(jié)點(diǎn)作為簇頭節(jié)點(diǎn) , 由簇頭節(jié)點(diǎn)形成一個(gè)處理 并轉(zhuǎn)發(fā)數(shù)據(jù)的骨干網(wǎng) , 其他非骨干網(wǎng)節(jié)點(diǎn)可以暫時(shí)關(guān)閉通 信模塊 , 進(jìn)入休眠狀態(tài)以節(jié)省能量。 功率控制 n 傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)發(fā)射功率的控制也稱功 率分配問題。節(jié)點(diǎn)通過設(shè)置或動(dòng)態(tài)調(diào)整節(jié) 點(diǎn)的發(fā)射功率 , 在保證網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)連通、 雙向連通 或者多連通 的基 礎(chǔ)上 , 使得 網(wǎng)絡(luò) 中節(jié)點(diǎn)的能量消耗最小 , 延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生 存時(shí)間。當(dāng) 傳感 器節(jié) 點(diǎn)部署 在二 維或三 維空 間中時(shí) , 傳感器網(wǎng)絡(luò)的功率控制是一 個(gè) NP 難 的問題 。因 此 , 一般的 解決 方 案都 是尋 找近似解

4、法。 NP難問題 NP難問題 功率控制算法 基于節(jié)點(diǎn)度的算法 n 一個(gè)節(jié)點(diǎn)的度數(shù)是指所有距離該節(jié)點(diǎn)一跳的鄰居節(jié)點(diǎn)的 數(shù)目。 n基于節(jié)點(diǎn)度算法的核心思想是給定節(jié)點(diǎn)度的上限和下限需 求 , 動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的發(fā)射功率 , 使得節(jié)點(diǎn)的度數(shù)落在上限 和下限之間?；诠?jié)點(diǎn)度的算法利用局部 信息 來調(diào) 整相 鄰 節(jié)點(diǎn) 間的連 通性 , 從 而保證整個(gè)網(wǎng)絡(luò)的連通性 , 同時(shí) 保證節(jié)點(diǎn)間的鏈路 具有一 定的 冗余 性和可 擴(kuò)展 性。 n本地平均算法 LM A ( local mean algorit hm ) 和 本 地鄰 居 平均 算 法 L MN ( local mean of neighbors algor

5、ithm ) 是兩種周期性動(dòng)態(tài)調(diào)整節(jié) 點(diǎn)發(fā) 射功 率的算 法。它們 之 的區(qū)別在于計(jì)算節(jié)點(diǎn)度的策略不同 本地平均算法（1） n( 1) 開始時(shí)所有節(jié)點(diǎn)都有相同的發(fā)射功率 TransPowe r , 每個(gè) 節(jié)點(diǎn)定期 廣播一 個(gè)包含己 ID 的 Life Msg 消息。 n( 2) 如果節(jié)點(diǎn)接收 到 LifeMs g 消 息 , 發(fā)送 一個(gè) LifeAckMsg 應(yīng) 答消 息。該 消 息中 包含所應(yīng)答 的 LifeMsg 消息中的節(jié)點(diǎn) ID。 n ( 3) 每個(gè)節(jié)點(diǎn)在下一次發(fā)送 LifeMsg 時(shí) , 首先檢 查 已經(jīng)收到 的 LifeAckM sg 消息 , 利用這些消息 統(tǒng)計(jì)出自己的鄰居數(shù) N

6、odeResp。 本地平均算法（2） n(4) 如果 NodeResp 小于鄰居數(shù)下限NodeMinThresh , 那 么節(jié)點(diǎn)在這輪發(fā)送中將增大發(fā)射功率 , 但發(fā)射功率不能超 過初始發(fā)射功率的 Bmax 倍 , 如式 (4-1 ) 所示; 同理 , 如果 NodeResp大于鄰居節(jié) 點(diǎn) 數(shù) 上 限 NodeMaxThresh , 那 么 節(jié)點(diǎn) 將 減 小 發(fā) 射功 率 , 用 式 (4-2) 表 示, 其 中Bm ax , Bmin , Ainc 和 Ade c 是四個(gè)可調(diào)參數(shù) , 它們會(huì)影響功 率調(diào)節(jié)的精度和范圍。 本 地鄰 居 平均 算 法 LMN n本地鄰居 平 均 算 法 L MN

7、與 本 地 平 均 算 法 L MA 類 似 , 惟 一 的 區(qū) 別 是 在 鄰 居 數(shù)NodeResp 的計(jì)算方法上。在 L MN 算法 中 , 每 個(gè)節(jié) 點(diǎn) 發(fā)送 LifeAckMsg 消 息 時(shí) , 將自己的鄰居數(shù)放入消息中 , 發(fā)送 LifeMsg 消息的節(jié)點(diǎn)在收集完所有 LifeAckMs g 消息后 , 將所有鄰居的鄰居數(shù) 求平均值并作為自己的鄰居數(shù)。 基于節(jié)點(diǎn)度的算法的優(yōu)缺點(diǎn) n這兩種算法都缺少嚴(yán)格的理論推導(dǎo)。通過計(jì)算機(jī) 仿真結(jié)果確定 : 這兩 種算法 的收斂性和網(wǎng)絡(luò)的連 通性是可以保證的 , 它們通過少量的局部信息達(dá) 到了一定程度的優(yōu)化效果。 n這兩種算法對(duì)無線傳感器節(jié)點(diǎn)的要求

8、不高 , 不 需 要嚴(yán) 格的 時(shí)鐘 同步。但 是算法 還存 在一些明 顯不完善的地方 , 例如 , 需要進(jìn)一步研究 合理的 鄰居 節(jié)點(diǎn)判 斷條 件 , 對(duì)從鄰 居節(jié) 點(diǎn)得到的信息 是否根據(jù)信號(hào)的強(qiáng)弱給予不同的權(quán)重等。 其它功率控制算法 n基于鄰近圖的算法 基于鄰近圖的算法 n 1 . 鄰近圖 n 基于鄰近圖的功率控制算法是指 : 所有節(jié)點(diǎn)都使用最 大功率發(fā)射時(shí)形成的拓?fù)鋱D為圖 G, 按照一定的規(guī)則 q 求出該圖的鄰近 圖 G 最 后 G 中每 個(gè)節(jié)點(diǎn) 以自 己 所鄰 接的 最遠(yuǎn)通信節(jié)點(diǎn)來確定發(fā)射功率。這是一種 解決功率分配問題的近似解法 ?？紤]到傳感器網(wǎng)絡(luò) 中兩個(gè)節(jié)點(diǎn)形成的邊是有向的 , 為了

9、避免形成單向邊 , 一般在運(yùn)用基于鄰近圖的算法形成網(wǎng)絡(luò)拓?fù)渲?后 , 還 需 要 進(jìn) 行 節(jié) 點(diǎn) 之 間 邊 的 增 刪 , 以 使 最 后 得 到 的 網(wǎng) 絡(luò) 拓 撲 是 雙 向 連通的。 nDRNG 算法和 DLSS 算法 層次型拓?fù)浣Y(jié)構(gòu)控制 n 在傳感器網(wǎng)絡(luò)中 , 傳感器節(jié)點(diǎn)的無線通信模塊 在空 閑狀 態(tài)時(shí)的 能 量 消耗與 在收 發(fā)狀態(tài)時(shí)相當(dāng) , 所以只有關(guān)閉節(jié)點(diǎn)的通信模塊 , 才 能 大幅 度地 降低無 線通 信模 塊的能 量開 銷。 n考慮依據(jù)一定機(jī)制選擇某些節(jié)點(diǎn)作為骨干網(wǎng)節(jié)點(diǎn) , 打開其通信模塊 , 并關(guān)閉非骨干節(jié)點(diǎn)的通信模塊 , 由骨干節(jié)點(diǎn)構(gòu)建一個(gè)連通網(wǎng)絡(luò)來負(fù) 責(zé) 數(shù)據(jù) 的路

10、由轉(zhuǎn) 發(fā)。這樣 既保證 了原 有覆蓋范圍內(nèi)的數(shù)據(jù)通信 , 也 在很大程度上節(jié)省了節(jié)點(diǎn)能量。在這種拓?fù)涔芾頇C(jī)制下 , 網(wǎng)絡(luò)中的節(jié) 點(diǎn)可以劃分為骨 干網(wǎng) 節(jié)點(diǎn) 和普 通節(jié) 點(diǎn) 兩類。骨 干 網(wǎng)節(jié) 點(diǎn)對(duì) 周圍 的普 通 節(jié)點(diǎn) 進(jìn)行 管轄。這類算法將整個(gè)網(wǎng)絡(luò)劃分為相連的區(qū) 域 , 一 般又 稱為 分簇 算法。骨 干網(wǎng)節(jié) 點(diǎn)是 簇頭節(jié)點(diǎn) , 普通節(jié)點(diǎn)是簇內(nèi)節(jié) 點(diǎn)。由于簇頭節(jié)點(diǎn)需要協(xié)調(diào)簇內(nèi)節(jié)點(diǎn)的工作 , 負(fù)責(zé)數(shù)據(jù)的融合和轉(zhuǎn)發(fā) , 能量消耗相對(duì)較大 , 所以分簇算法通常采用周期性地選擇簇頭節(jié)點(diǎn)的 做法以均衡網(wǎng)絡(luò)中的節(jié)點(diǎn)能量消耗。 優(yōu)點(diǎn) n層 次型的 拓?fù)?結(jié)構(gòu)具 有很 多優(yōu) 點(diǎn) , 例 如 , 由 簇 頭

11、節(jié) 點(diǎn) 擔(dān)負(fù) 數(shù) 據(jù) 融 合 的任 務(wù) , 減 少 了數(shù) 據(jù)通信 量 ; 分 簇式的 拓 撲 結(jié) 構(gòu) 有 利 于 分 布 式 算 法 的 應(yīng) 用 , 適 合 大 規(guī) 模 部 署 的 網(wǎng) 絡(luò) ;由 于大部 分節(jié) 點(diǎn)在相 當(dāng)長(zhǎng) 的時(shí) 間內(nèi)關(guān) 閉通 信模 塊 , 所 以 顯 著地 延 長(zhǎng) 整 個(gè) 網(wǎng)絡(luò) 的 生 存 時(shí)間 等。 層次型拓?fù)浣Y(jié)構(gòu)控制 nLEACH 算法 nGAF 算法 nGAF 改進(jìn)算法 nTopDisc 算法 (三色算法，四 色算法） 啟發(fā)機(jī)制 n 傳感器網(wǎng)絡(luò)通常是面向應(yīng)用的事件驅(qū)動(dòng)的 網(wǎng)絡(luò) , 骨 干網(wǎng) 節(jié)點(diǎn)在 沒 有 檢測(cè)到 事件 時(shí)不必一直保持在活動(dòng)狀態(tài)。在傳感器網(wǎng)絡(luò)的拓?fù)?控

12、制 算法 中 , 除了傳 統(tǒng)的 功率控 制和 層次型拓?fù)淇刂苾蓚€(gè)方面之外 , 也提出了啟發(fā)式的 節(jié)點(diǎn)喚 醒和 休眠 機(jī)制。該 機(jī)制能 夠使 節(jié)點(diǎn)在沒 有事件發(fā)生時(shí)設(shè)置通信模塊為睡眠狀態(tài) , 而在 有事 件發(fā) 生時(shí)及 時(shí)自 動(dòng)醒來 并喚 醒鄰居節(jié)點(diǎn) , 形成數(shù)據(jù)轉(zhuǎn)發(fā)的拓?fù)浣Y(jié)構(gòu)。這種機(jī)制的引 入 , 使得無線通信模塊大部分時(shí)間都處于關(guān)閉狀態(tài) , 只有傳感器模塊 處于工作狀態(tài)。由于 無線 通信 模塊消 耗的 能量遠(yuǎn) 大于 傳感器模塊 , 所以這進(jìn)一步節(jié)省了能量開銷。這種機(jī)制 重點(diǎn) 在于 解決節(jié) 點(diǎn)在 睡 眠狀 態(tài)和 活動(dòng)狀態(tài)之間的轉(zhuǎn)換問題 , 不能夠獨(dú)立作為一種拓?fù)浣Y(jié)構(gòu) 控制機(jī)制 , 需要與其他拓?fù)淇刂扑惴ńY(jié)合使用。 啟發(fā)機(jī)制 nSTEM 算法:（S T E M-B 和 ST E M-T算法） n2 . STEM-T( STEM-TONE) 算法 ASCENT 算法 n 在功率控制方面提出了以鄰居節(jié)點(diǎn)度為參考依據(jù)算法，以及利 用鄰近圖思想生成拓?fù)浣Y(jié)構(gòu)的算法； n 在層次型拓?fù)淇刂品矫嫣岢隽撕芏喾执厮惴ā?n 但是其中大多數(shù)算法停留在理淪研究階段或者只做過少量節(jié)點(diǎn) 的模擬，沒有充分考慮實(shí)際應(yīng)用的諸多困難，例如，節(jié)點(diǎn)大規(guī) 模撤布時(shí)，如何保證算法的收斂速度，如何減小外界因素對(duì)通 信的干擾，以及節(jié)點(diǎn)失