無(wú)線傳感器網(wǎng)絡(luò) Wireless Sensor Networks(WSNs)

《無(wú)線傳感器網(wǎng)絡(luò) Wireless Sensor Networks(WSNs)》由會(huì)員分享，可在線閱讀，更多相關(guān)《無(wú)線傳感器網(wǎng)絡(luò) Wireless Sensor Networks(WSNs)（171頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、無(wú) 線 傳 感 器 網(wǎng) 絡(luò)Wireless Sensor Networks（ WSNs） 1. 無(wú) 線 傳 感 器 網(wǎng) 絡(luò) 概 述 無(wú) 線 傳 感 器 網(wǎng) 絡(luò) 通 常 由 大 量 具 有 感 知 、 計(jì) 算 及 無(wú) 線 通 信能 力 的 微 小 節(jié) 點(diǎn) 組 成 ， 其 目 的 是 監(jiān) 視 環(huán) 境 而 非 通 信 。 傳 感 器 節(jié) 點(diǎn) 部 署 在 要 監(jiān) 視 的 區(qū) 域 中 ， 采 集 指 定 的 環(huán) 境 參數(shù) ， 并 將 數(shù) 據(jù) 發(fā) 送 到 匯 聚 節(jié) 點(diǎn) 供 分 析 。 傳 感 器 節(jié) 點(diǎn) 的 組 成 傳 感 器 節(jié) 點(diǎn) 一 般 由 傳 感 模 塊 、 處 理 模 塊 、 無(wú) 線 通 信

2、模 塊 和 能 量供 應(yīng) 模 塊 組 成 。 傳 感 器 節(jié) 點(diǎn) 已 經(jīng) 可 以 做 得 非 常 小 ， 稱 為 智 能 塵 埃 （ smart dust） 。 傳 感 器 節(jié) 點(diǎn) 的 特 點(diǎn) 廉 價(jià) ： 每 個(gè) 節(jié) 點(diǎn) 的 期 望 價(jià) 格 在 一 美 元 左 右 體 積 小 ： 火 柴 盒 或 硬 幣 般 大 小 重 量 輕 ： 小 于 100克 能 量 有 限 ： 兩 節(jié) 五 號(hào) 電 池 或 紐 扣 電 池 供 電 無(wú) 線 通 信 能 力 ： 能 夠 用 無(wú) 線 電 、 紅 外 線 、 藍(lán) 牙 、 超聲 波 等 通 信 ， 帶 寬 低 ， 干 擾 大 計(jì) 算 能 力 ： 幾 百 兆 赫 茲

3、 的 處 理 器 存 儲(chǔ) 能 力 ： 幾 兆 或 幾 百 兆 的 存 儲(chǔ) 空 間 感 知 能 力 ： 具 有 一 個(gè) 或 幾 個(gè) 傳 感 器 軟 件 環(huán) 境 ： TinyOS是 專(zhuān) 為 傳 感 器 節(jié) 點(diǎn) 開(kāi) 發(fā) 的 操 作 系統(tǒng) 傳 感 器 網(wǎng) 絡(luò) 的 特 點(diǎn) 節(jié) 點(diǎn) 固 定 或 只 有 較 小 的 活 動(dòng) 性 數(shù) 量 大 ， 密 度 高 拓 撲 動(dòng) 態(tài) 變 化 節(jié) 點(diǎn) 同 構(gòu) ， 或 只 有 少 量 特 殊 節(jié) 點(diǎn) ； 分 布 式 ： 沒(méi) 有 預(yù) 先 指 定 的 中 心 ， 所 有 節(jié) 點(diǎn) 通 過(guò) 分 布式 算 法 相 互 協(xié) 調(diào) ； 自 組 織 ： 傳 感 器 網(wǎng) 絡(luò) 的 部 署 和 初

4、 始 化 等 不 需 要 外 界干 預(yù) ； 節(jié) 點(diǎn) 資 源 受 限 ， 特 別 是 能 量 非 常 有 限 ； 以 數(shù) 據(jù) 為 中 心 的 網(wǎng) 絡(luò) ， 節(jié) 點(diǎn) 具 有 數(shù) 據(jù) 處 理 的 能 力 ； 與 應(yīng) 用 緊 密 耦 合 的 網(wǎng) 絡(luò) 傳 感 器 網(wǎng) 絡(luò) 與 移 動(dòng) 自 組 網(wǎng) 的 不 同 節(jié) 點(diǎn) 規(guī) 模 ：l 移 動(dòng) 自 組 網(wǎng) ： 節(jié) 點(diǎn) 數(shù) 量 通 常 在 幾 十 或 上 百l 傳 感 器 網(wǎng) 絡(luò) ： 節(jié) 點(diǎn) 數(shù) 目 往 往 高 出 好 幾 個(gè) 數(shù) 量 級(jí) 節(jié) 點(diǎn) 密 度 ：l 移 動(dòng) 自 組 網(wǎng) ： 小l 傳 感 器 網(wǎng) 絡(luò) ： 大 （ 冗 余 部 署 的 結(jié) 果 ） 拓 撲 變

5、化 的 原 因 ：l 移 動(dòng) 自 組 網(wǎng) ： 節(jié) 點(diǎn) 運(yùn) 動(dòng) l 傳 感 器 網(wǎng) 絡(luò) ： 節(jié) 點(diǎn) 休 眠 調(diào) 度 、 環(huán) 境 干 擾 或 節(jié) 點(diǎn) 故 障 引 起 節(jié) 點(diǎn) 處 理 能 力 ：l 移 動(dòng) 自 組 網(wǎng) ： 較 強(qiáng)l 傳 感 器 網(wǎng) 絡(luò) ： 十 分 有 限 傳 感 器 網(wǎng) 絡(luò) 的 應(yīng) 用 傳 感 器 網(wǎng) 絡(luò) 在 環(huán) 境 監(jiān) 視 方 面 的 優(yōu) 勢(shì) ：l 通 過(guò) 在 物 理 環(huán) 境 中 部 署 大 量 廉 價(jià) 的 智 能 傳 感 器 節(jié) 點(diǎn) ， 可以 獲 得 長(zhǎng) 時(shí) 間 、 近 距 離 、 高 分 辨 率 的 環(huán) 境 數(shù) 據(jù) ， 這 是 傳統(tǒng) 監(jiān) 視 設(shè) 備 無(wú) 法 得 到 的 。l 傳

6、 感 器 節(jié) 點(diǎn) 的 計(jì) 算 和 存 儲(chǔ) 能 力 允 許 節(jié) 點(diǎn) 執(zhí) 行 數(shù) 據(jù) 過(guò) 濾 、數(shù) 據(jù) 壓 縮 等 操 作 ， 也 可 以 執(zhí) 行 一 些 應(yīng) 用 特 定 的 處 理 任 務(wù) 。l 節(jié) 點(diǎn) 之 間 的 通 信 能 力 允 許 節(jié) 點(diǎn) 之 間 協(xié) 同 完 成 更 復(fù) 雜 的 任務(wù) ， 如 目 標(biāo) 跟 蹤 。 l 通 過(guò) 任 務(wù) 的 重 新 分 配 可 以 改 變 傳 感 器 網(wǎng) 絡(luò) 的 用 途 。 （ 1） 監(jiān) 視 紅 杉 樹(shù) 的 小 氣 候 1 在 一 棵 紅 杉 樹(shù) 的 不 同 位 置 安 裝 無(wú) 線 氣 象 站進(jìn) 行 數(shù) 據(jù) 采 集 ， 如 光 輻 射 、 溫 度 、 濕 度

7、、氣 壓 ， 形 成 森 林 氣 候 一 個(gè) 樣 本 。 可 在 森 林 的 不 同 地 方 （ 如 森 林 的 中 心 處 、迎 風(fēng) 面 、 背 風(fēng) 面 、 向 陽(yáng) 面 等 ） 部 署 這 樣 的傳 感 器 網(wǎng) 絡(luò) ， 然 后 利 用 長(zhǎng) 距 離 上 行 鏈 路 將數(shù) 據(jù) 發(fā) 送 到 匯 聚 節(jié) 點(diǎn) 。 無(wú) 線 氣 象 站 （ 傳 感 器 節(jié) 點(diǎn) ） 實(shí) 驗(yàn) 結(jié) 果 片 段 （ 2） 監(jiān) 視 地 下 結(jié) 構(gòu) 的 改 變 2 將 傳 感 器 節(jié) 點(diǎn) 固 定 放 置 在 坑 頂 和 坑 壁 上 形 成 規(guī) 則 的 網(wǎng)狀 網(wǎng) 絡(luò) （ 蜂 窩 狀 六 邊 形 ） ， 每 個(gè) 節(jié) 點(diǎn) 預(yù) 先 設(shè) 置

8、好 位 置 ，每 個(gè) 節(jié) 點(diǎn) 都 知 道 自 己 的 鄰 居 集 合 ， 并 定 期 與 鄰 居 交 換信 標(biāo) 。 當(dāng) 發(fā) 生 坍 塌 時(shí) ， 坍 塌 區(qū) 域 內(nèi) 的 節(jié) 點(diǎn) 發(fā) 生 移 位 ， 在 網(wǎng) 絡(luò)中 形 成 空 洞 。 當(dāng) 一 個(gè) 節(jié) 點(diǎn) 發(fā) 現(xiàn) 它 的 一 些 鄰 居 突 然 消 失時(shí) （ 收 聽(tīng) 不 到 信 標(biāo) ） ， 判 斷 自 己 成 為 空 洞 的 一 個(gè) 邊 界節(jié) 點(diǎn) ， 向 匯 聚 節(jié) 點(diǎn) 報(bào) 告 自 己 的 位 置 。 匯 聚 節(jié) 點(diǎn) 計(jì) 算 空 洞 區(qū) 域 。 （ 3） 人 居 環(huán) 境 監(jiān) 視 3 在 一 個(gè) 標(biāo) 準(zhǔn) 的 電 源 插 線 板 上 擴(kuò) 充 了 各 種

9、傳 感器 和 無(wú) 線 收 發(fā) 器 ， 一 個(gè) 微 處 理 器 控 制 所 有 的部 件 ， 成 為 一 個(gè) plug節(jié) 點(diǎn) 。 利 用 plug節(jié) 點(diǎn) 的 多 模 式 感 知 能 力 ， 可 以 較準(zhǔn) 確 地 推 斷 發(fā) 生 的 事 件 。 所 有 plug節(jié) 點(diǎn) 構(gòu) 成 普 適 計(jì) 算 環(huán) 境 中 的 骨 干網(wǎng) ， 可 以 了 解 到 plug網(wǎng) 絡(luò) 所 在 環(huán) 境 的 活 動(dòng)情 況 無(wú) 線 傳 感 器 網(wǎng) 絡(luò) 要 解 決 的 問(wèn) 題 網(wǎng) 絡(luò) 的 自 組 織 、 自 配 置 （ 節(jié) 點(diǎn) 定 位 、 時(shí) 間同 步 、 自 動(dòng) 校 準(zhǔn) 、 拓 撲 控 制 等 ） 通 信 協(xié) 議 （ MAC、 路

10、 由 協(xié) 議 ） 分 布 式 數(shù) 據(jù) 管 理 （ 數(shù) 據(jù) 采 集 、 存 儲(chǔ) 、 查 詢 、獲 取 等 ） 各 種 應(yīng) 用 特 定 的 數(shù) 據(jù) 融 合 處 理 節(jié) 省 能 耗 應(yīng) 貫 穿 到 所 有 的 設(shè) 計(jì) 中 。 2. 節(jié) 點(diǎn) 定 位 節(jié) 點(diǎn) 定 位 是 傳 感 器 網(wǎng) 絡(luò) 的 重 要 基 礎(chǔ) 功 能 ， 沒(méi) 有 位置 信 息 的 環(huán) 境 數(shù) 據(jù) 是 沒(méi) 有 意 義 的 。 手 工 為 每 個(gè) 節(jié) 點(diǎn) 設(shè) 定 位 置 不 可 能 ， GPS定 位 系 統(tǒng)無(wú) 法 大 規(guī) 模 應(yīng) 用 到 傳 感 器 節(jié) 點(diǎn) 上 。 傳 感 器 節(jié) 點(diǎn) 依 靠 相 互 之 間 的 協(xié) 作 來(lái) 確 定 各 自

11、物 理位 置 的 過(guò) 程 ， 稱 為 節(jié) 點(diǎn) 定 位 。 節(jié) 點(diǎn) 定 位 算 法 的 分 類(lèi) 絕 對(duì) 定 位 和 相 對(duì) 定 位 ：l 絕 對(duì) 定 位 ： 網(wǎng) 絡(luò) 中 存 在 已 知 位 置 的 參 考 節(jié) 點(diǎn)（ 錨 節(jié) 點(diǎn) ） ， 所 有 節(jié) 點(diǎn) 根 據(jù) 參 考 節(jié) 點(diǎn) 確 定 自 己的 位 置 ， 所 有 節(jié) 點(diǎn) 使 用 同 一 個(gè) 坐 標(biāo) 系 。l 相 對(duì) 定 位 ： 網(wǎng) 絡(luò) 中 不 存 在 已 知 位 置 的 參 考 節(jié) 點(diǎn) ，所 有 節(jié) 點(diǎn) 確 定 到 其 它 節(jié) 點(diǎn) 的 相 對(duì) 位 置 。 基 于 測(cè) 距 的 定 位 和 非 基 于 測(cè) 距 的 定 位 ：l 基 于 測(cè) 距 的 定

12、 位 ： 借 助 于 節(jié) 點(diǎn) 之 間 的 距 離 信 息或 角 度 信 息 進(jìn) 行 位 置 估 計(jì) ； l 非 基 于 測(cè) 距 的 定 位 ： 不 需 要 或 不 直 接 測(cè) 量 節(jié) 點(diǎn)之 間 的 距 離 及 角 度 信 息 。 衡 量 定 位 算 法 的 性 能 指 標(biāo) 平 均 定 位 誤 差 ： 待 定 位 節(jié) 點(diǎn) 的 估 測(cè) 位 置 到實(shí) 際 位 置 的 平 均 距 離 。 可 定 位 節(jié) 點(diǎn) 的 比 率 算 法 復(fù) 雜 度 （ 計(jì) 算 、 通 信 ） 收 斂 速 度 健 壯 性 2.1 測(cè) 距 技 術(shù) 大 多 數(shù) 已 有 的 位 置 發(fā) 現(xiàn) 方 法 由 兩 個(gè) 基 本 的 階 段 組

13、成 ：l 距 離 （ 或 角 度 ） 估 計(jì)l 距 離 （ 或 角 度 ） 融 合 估 計(jì) 兩 個(gè) 節(jié) 點(diǎn) 間 距 離 最 常 用 的 方 法 是 ：l 接 收 信 號(hào) 強(qiáng) 度 指 示 RSSI： 根 據(jù) 接 收 到 的 信 號(hào) 強(qiáng) 度 計(jì) 算 路徑 損 耗 ， 再 將 路 徑 損 耗 轉(zhuǎn) 換 成 距 離 。l 基 于 時(shí) 間 的 方 法 （ ToA、 TDoA） ： 根 據(jù) 信 號(hào) 到 達(dá) 時(shí) 間 或兩 種 信 號(hào) 的 到 達(dá) 時(shí) 間 差 估 算 距 離 。 l 到 達(dá) 角 度 AoA： 估 計(jì) 信 號(hào) 的 到 達(dá) 角 度 ， 用 幾 何 關(guān) 系 計(jì) 算 節(jié)點(diǎn) 位 置 。 RSSI（ Rec

14、eived Signal Strength Indicator） 已 知 發(fā) 射 節(jié) 點(diǎn) 的 發(fā) 射 功 率 ， 接 收 節(jié) 點(diǎn) 根 據(jù) 接 收 到 的 信號(hào) 強(qiáng) 度 估 算 到 發(fā) 射 節(jié) 點(diǎn) 的 距 離 。 使 用 最 廣 泛 的 信 號(hào) 傳 播 模 型 是 對(duì) 數(shù) 距 離 路 徑 損 耗 模 型 ，其 中 功 率 均 用 分 貝 表 示 ： 大 量 研 究 表 明 ， 在 無(wú) 線 傳 感 器 網(wǎng) 絡(luò) 中 無(wú) 法 得 到 信 號(hào) 衰減 與 距 離 之 間 的 一 致 模 型 ， 主 要 原 因 在 于 ： l 環(huán) 境 的 影 響 ： 多 路 徑 、 衰 落 、 遮 蔽 效 應(yīng)l 天 線 高

15、 度l 節(jié) 點(diǎn) 的 發(fā) 射 功 率 未 精 確 校 準(zhǔn) TDoA（ Time Difference of Arrival） 發(fā) 送 節(jié) 點(diǎn) 同 時(shí) 發(fā) 出 射 頻 及 超 聲 波 兩 種 信 號(hào) ， 接 收 節(jié) 點(diǎn) 根 據(jù) 收 到 兩 種 信 號(hào)的 時(shí) 間 差 來(lái) 估 算 距 離 。 特 點(diǎn) ：l 精 度 高l 傳 輸 特 性 也 受 環(huán) 境 影 響 ， 但 較 易 檢 測(cè)l 超 聲 傳 輸 距 離 短 RSSI與 TDoA的 比 較 4 AoA（ Angle of Arrival） 5 通 過(guò) 陣 列 天 線 或 多 個(gè) 接 收 器 得到 信 號(hào) 到 達(dá) 的 方 向 。 圖 示 的 例 子

16、中 同 時(shí) 使 用 到 達(dá) 信號(hào) 的 時(shí) 間 差 （ TDoA） 和 相 位差 ：l 使 用 兩 個(gè) 超 聲 信 號(hào) 接 收 器 ， 相距 L放 置 ；l 利 用 TDoA得 到 兩 個(gè) 超 聲 信 號(hào)接 收 器 到 發(fā) 送 節(jié) 點(diǎn) 的 距 離 x1和 x2； l 利 用 x1、 x2和 L計(jì) 算 到 發(fā) 送 節(jié)點(diǎn) 的 角 度 。 2.2 距 離 （ 角 度 ） 融 合 距 離 （ 角 度 ） 融 合 常 用 的 方 法 是 ：l 三 邊 測(cè) 量 法 （ tri-lateration） ： 通 過(guò) 計(jì) 算 3個(gè)圓 的 交 點(diǎn) 來(lái) 定 位 節(jié) 點(diǎn) 。l 三 角 測(cè) 量 法 （ triangula

17、tion） ： 使 用 三 角 函 數(shù)來(lái) 計(jì) 算 節(jié) 點(diǎn) 位 置 。l 最 大 似 然 估 計(jì) 法 （ Maximum Likelihood estimation） ： 通 過(guò) 最 小 化 測(cè) 量 距 離 和 估 計(jì) 距離 之 間 的 差 異 來(lái) 估 計(jì) 節(jié) 點(diǎn) 位 置 距 離 （ 角 度 ） 融 合 的 圖 示 三 角 測(cè) 量 轉(zhuǎn) 化 為 多 邊 測(cè) 量 知 道 參 考 節(jié) 點(diǎn) A、 B的 位置 及 未 知 節(jié) 點(diǎn) D到 AB的角 度 ， 則 D位 于 以 O為 圓心 的 圓 周 上 ， 其 中 AOB = 2 ADB。 對(duì) 于 每 一 對(duì) 參 考 節(jié) 點(diǎn) A、B， 計(jì) 算 出 O的 位 置

18、 和 半徑 ， 列 出 圓 方 程 ， 從 而將 三 角 測(cè) 量 問(wèn) 題 轉(zhuǎn) 化 為多 邊 測(cè) 量 問(wèn) 題 。 最 大 似 然 估 計(jì) 位 于 （ x0, y0） 的 待 定 位 節(jié) 點(diǎn) 測(cè) 得 到 N個(gè) 參 考 節(jié) 點(diǎn) 的 距 離 為d1dN， 若 位 置 及 距 離 是 精 確 的 ， 則 有 ： 在 有 噪 聲 的 環(huán) 境 下 （ 位 置 或 測(cè) 距 有 誤 差 ） ， 以 上 方 程 可 能 沒(méi) 有解 （ N個(gè) 圓 不 交 于 一 點(diǎn) ） ， 可 采 用 最 小 均 方 估 計(jì) 來(lái) 獲 得 最 佳 的位 置 估 計(jì) 值 ： 線 性 化 求 解 將 等 式 （ 2-1） 的 兩 邊 分

19、別 相 加 ： 將 等 式 （ 2-1） 減 去 等 式 （ 2-3） ， 得 到 N個(gè) 線 性 方 程 ： 以 上 方 程 組 可 以 寫(xiě) 為 y=bX， 其 中 b為 (x0,y0)T ， X為 系 數(shù) 矩 陣 ， y為 常 數(shù) 矢 量 ， 則 b=(XTX)-1XTy。 2.3 Ad-Hoc Localization System（ AHLoS） 4 AHLoS是 一 個(gè) 基 于 TDoA和 多 邊 測(cè) 量 的 定 位 算法 ， 也 稱 迭 代 多 邊 測(cè) 量 法 ：l 參 考 節(jié) 點(diǎn) 向 鄰 居 節(jié) 點(diǎn) 廣 播 自 己 的 位 置 ；l 未 知 節(jié) 點(diǎn) 測(cè) 量 到 鄰 居 參 考 節(jié)

20、點(diǎn) 的 距 離 ， 若 滿 足 多 邊測(cè) 量 的 條 件 （ 至 少 在 3個(gè) 參 考 節(jié) 點(diǎn) 的 通 信 距 離 內(nèi) ） ，利 用 多 邊 測(cè) 量 法 估 計(jì) 自 己 的 位 置 ；l 一 旦 未 知 節(jié) 點(diǎn) 確 定 了 自 己 的 位 置 后 ， 就 成 為 新 的 參考 節(jié) 點(diǎn) ， 向 其 鄰 居 節(jié) 點(diǎn) 廣 播 自 己 的 位 置 ； l 這 個(gè) 過(guò) 程 不 斷 重 復(fù) ， 直 至 所 有 滿 足 多 邊 測(cè) 量 條 件 的未 知 節(jié) 點(diǎn) 都 獲 得 自 己 的 位 置 。 原 子 多 邊 測(cè) 量 未 知 節(jié) 點(diǎn) （ x0,y0） 到 第 i個(gè) 參 考 節(jié) 點(diǎn) 的 距 離 方 程 表

21、示 為 ： (xi-x0)2 + (yi-y0)2 = (stio)2 或 若 有 k個(gè) 這 樣 的 方 程 ， 從 其 它 方 程 中 減 去 第 k個(gè) 方 程 ，可 得 到 以 下 線 性 方 程 ： 該 方 程 組 可 表 示 成 y=bX的 形 式 ， 并 有 b=(XTX)-1XTy， 其 中 ： 協(xié) 同 多 邊 測(cè) 量 原 子 多 邊 測(cè) 量 需 要 滿 足 的條 件 是 ：l 未 知 節(jié) 點(diǎn) 至 少 有 3個(gè) 參考 節(jié) 點(diǎn) 鄰 居 。 協(xié) 同 多 邊 測(cè) 量 ：l 未 知 節(jié) 點(diǎn) 利 用 距 其 多跳 的 參 考 節(jié) 點(diǎn) 位 置 估計(jì) 自 己 的 位 置 ， 同 時(shí)可 以 估 算

22、 出 其 它 一 些未 知 節(jié) 點(diǎn) 的 位 置 。 協(xié) 同 多 邊 測(cè) 量 的 問(wèn) 題 描 述 將 傳 感 器 網(wǎng) 絡(luò) 抽 象 為 一 個(gè) 連 通 的 無(wú) 向 圖 G=（ N, E） ，信 標(biāo) 節(jié) 點(diǎn) 集 合 用 B表 示 ， 未 知 節(jié) 點(diǎn) 集 合 用 U表 示 ， 我 們的 目 標(biāo) 是 求 解 ： 參 與 節(jié) 點(diǎn) 與 參 與 節(jié) 點(diǎn) 對(duì) 定 義 1：l 一 個(gè) 節(jié) 點(diǎn) 是 參 與 節(jié) 點(diǎn) ， 如 果 它 是 一 個(gè) 參 考 節(jié) 點(diǎn) ，或 者 是 一 個(gè) 至 少 有 3個(gè) 參 與 鄰 居 的 未 知 節(jié) 點(diǎn) 。 定 義 2：l 一 個(gè) 參 與 節(jié) 點(diǎn) 對(duì) 是 一 對(duì) 連 通 的 參 考 節(jié)

23、點(diǎn) -未 知 節(jié)點(diǎn) 或 未 知 節(jié) 點(diǎn) -未 知 節(jié) 點(diǎn) ， 其 中 所 有 未 知 節(jié) 點(diǎn) 均為 參 與 節(jié) 點(diǎn) 。 2.4 不 基 于 測(cè) 距 的 （ rang-free） 定 位 算 法 不 基 于 測(cè) 距 的 算 法 不 需 要 知 道 待 定 位 節(jié) 點(diǎn) 到參 考 節(jié) 點(diǎn) 的 距 離 ， 或 者 不 需 要 直 接 測(cè) 量 此 距離 ， 成 本 和 功 耗 較 低 。 幾 種 典 型 的 不 基 于 測(cè) 距 的 定 位 算 法 ：l 質(zhì) 心 法 （ Centroid）l 幾 何 約 束 法 （ Geomentic Consrain） l DV-HOP （ 1） 質(zhì) 心 法 6 質(zhì) 心

24、 法 基 于 以 下 兩 個(gè) 假 設(shè) ：l 射 頻 信 號(hào) 的 傳 播 遵 循 理 想 的 圓 球 模 型l 所 有 節(jié) 點(diǎn) 的 通 信 距 離 相 等 網(wǎng) 絡(luò) 中 放 置 了 固 定 數(shù) 量 、 通 信 區(qū) 域 相 重 疊 的 一 組 參 考節(jié) 點(diǎn) ， 這 些 參 考 節(jié) 點(diǎn) 構(gòu) 成 規(guī) 則 的 網(wǎng) 狀 結(jié) 構(gòu) 。 質(zhì) 心 法 （ 續(xù) ） 參 考 節(jié) 點(diǎn) 周 期 性 地 發(fā) 送 包 含 自 射 位 置 信 息 的 信 標(biāo) 消 息 ； 未 知 節(jié) 點(diǎn) 在 一 個(gè) 給 定 的 時(shí) 間 間 隔 t內(nèi) 接 收 信 標(biāo) 消 息 ， 對(duì) 于 每 個(gè)參 考 節(jié) 點(diǎn) Ri， 統(tǒng) 計(jì) 在 該 時(shí) 間 內(nèi) 收

25、到 的 信 標(biāo) 消 息 數(shù) Nrecv(i,t)，計(jì) 算 對(duì) 應(yīng) 的 連 接 測(cè) 度 CMi ： CMi = Nrecv(i,t) / Nsent(i,t) 100% 未 知 節(jié) 點(diǎn) 選 擇 連 接 測(cè) 度 大 于 指 定 閾 值 的 參 考 節(jié) 點(diǎn) （ 設(shè) 為 k個(gè) ） ，計(jì) 算 這 些 參 考 節(jié) 點(diǎn) 的 質(zhì) 心 作 為 自 己 的 位 置 估 計(jì) 值 ： （ 2） 幾 何 約 束 法 7 每 個(gè) 節(jié) 點(diǎn) 的 信 號(hào) 覆 蓋 范 圍 可 以 用 一 個(gè) 幾 何 形狀 來(lái) 表 示 幾 何 約 束 法 （ 續(xù) ） 對(duì) 于 每 個(gè) 聽(tīng) 到 的 參 考 節(jié) 點(diǎn) ， 待 定 位 節(jié) 點(diǎn) 計(jì) 算 這

26、些 參 考節(jié) 點(diǎn) 信 號(hào) 覆 蓋 范 圍 的 重 疊 區(qū) 域 。 幾 何 約 束 法 （ 續(xù) ） 計(jì) 算 包 含 重 疊 區(qū) 域 的 最 小 矩 形 ， 矩 形 的 中 心 作 為 節(jié) 點(diǎn)的 位 置 估 計(jì) 值 。 （ 3） 基 于 DV的 定 位 算 法 8 如 何 在 參 考 節(jié) 點(diǎn) 稀 疏 的 網(wǎng) 絡(luò) 中 進(jìn) 行 節(jié) 點(diǎn) 定 位 ？ 基 本 思 想 ：l 參 考 節(jié) 點(diǎn) 附 近 的 節(jié) 點(diǎn) 通 過(guò) 直 接 測(cè) 量 的 方 法 獲 得 到參 考 節(jié) 點(diǎn) 的 距 離 ， 傳 播 給 其 鄰 居 節(jié) 點(diǎn) ；l 鄰 居 節(jié) 點(diǎn) 據(jù) 此 估 計(jì) 自 己 到 參 考 節(jié) 點(diǎn) 的 距 離 ， 再 傳

27、播給 其 鄰 居 ； 依 次 類(lèi) 推 。 l 類(lèi) 似 于 距 離 矢 量 路 由 算 法 中 的 距 離 傳 播 ， 因 此 稱 這一 類(lèi) 方 法 為 基 于 DV的 方 法 。 DV-HOP傳 播 模 式 參 考 節(jié) 點(diǎn) 向 其 鄰 居 廣 播 信 標(biāo) 消 息 ， 所 有 節(jié) 點(diǎn) 維 護(hù) 到 每個(gè) 參 考 節(jié) 點(diǎn) 的 最 小 跳 數(shù) ， 并 與 鄰 居 節(jié) 點(diǎn) 交 換 各 自 的 距離 矢 量 表 。 參 考 節(jié) 點(diǎn) 利 用 其 它 參 考 節(jié) 點(diǎn) 的 位 置 及 自 己 到 這 些 參 考節(jié) 點(diǎn) 的 最 小 跳 數(shù) 計(jì) 算 每 跳 平 均 距 離 ， 發(fā) 布 到 網(wǎng) 絡(luò) 中 。 未 知 節(jié)

28、 點(diǎn) 根 據(jù) 其 最 近 的 參 考 節(jié) 點(diǎn) 發(fā) 布 的 平 均 每 跳 距 離 ，計(jì) 算 到 各 個(gè) 參 考 節(jié) 點(diǎn) 的 距 離 ， 使 用 多 邊 測(cè) 量 法 估 計(jì) 自己 的 位 置 。 DV-Distance傳 播 模 式 類(lèi) 似 于 DV-HOP， 但 該 算 法 傳 播 的 是 累 計(jì)距 離 ， 而 非 累 計(jì) 跳 數(shù) 。 該 方 法 比 DV-HOP精 確 一 些 ， 但 對(duì) 測(cè) 距 誤差 很 敏 感 。 Euclidean傳 播 模 式 該 方 法 傳 播 到 參 考 節(jié) 點(diǎn) 的 物 理 距 離 。 未 知 節(jié) 點(diǎn) A至 少 要 有 兩 個(gè) 鄰 居 B和 C， 且 B和 C都

29、有 到 參 考 節(jié)點(diǎn) L的 物 理 距 離 估 計(jì) ， 另 外 A測(cè) 量 到 B和 C的 距 離 ， 且 必 須 知道 距 離 BC。 這 樣 A可 以 計(jì) 算 距 離 AL。 2.5 安 全 定 位 大 多 數(shù) 通 用 的 定 位 算 法 未 考 慮 安 全 問(wèn) 題 ， 在出 現(xiàn) 距 離 或 位 置 欺 騙 的 情 況 下 ， 無(wú) 法 正 確 定位 。 已 有 的 一 些 安 全 定 位 算 法 通 用 性 較 差 ， 只 能對(duì) 付 一 種 或 幾 種 特 定 的 攻 擊 。 問(wèn) 題 ：l 能 否 找 到 一 種 統(tǒng) 一 的 方 法 來(lái) 抵 御 所 有 的 節(jié) 點(diǎn) 定 位攻 擊 ？ 從 統(tǒng)

30、計(jì) 的 角 度 看 節(jié) 點(diǎn) 定 位 問(wèn) 題 11 各 種 攻 擊 手 段 最 終 都 是 要 欺 騙 未 知 節(jié) 點(diǎn) 得 到 錯(cuò) 誤 的參 考 位 置 、 距 離 、 角 度 等 信 息 。 節(jié) 點(diǎn) 出 現(xiàn) 異 常 、 局 部 環(huán) 境 干 擾 等 因 素 也 會(huì) 導(dǎo) 致 未 知節(jié) 點(diǎn) 獲 得 錯(cuò) 誤 信 息 。 正 常 節(jié) 點(diǎn) 產(chǎn) 生 的 測(cè) 量 樣 本 也 是 有 誤 差 的 。 如 果 將 錯(cuò) 誤 及 誤 差 都 看 成 噪 聲 ， 未 知 節(jié) 點(diǎn) 的 任 務(wù) 就是 要 根 據(jù) 給 定 的 一 組 有 噪 聲 樣 本 進(jìn) 行 盡 可 能 準(zhǔn) 確 的位 置 估 計(jì) 。 這 樣 ， 我 們 就

31、 將 應(yīng) 對(duì) 定 位 攻 擊 、 節(jié) 點(diǎn) 異 常 和 環(huán) 境 干擾 的 問(wèn) 題 統(tǒng) 一 轉(zhuǎn) 化 為 在 測(cè) 量 樣 本 集 中 去 除 大 噪 聲 樣本 的 問(wèn) 題 。 問(wèn) 題 描 述 由 未 知 節(jié) 點(diǎn) 和 若 干 參 考 節(jié) 點(diǎn) 組 成 的 傳 感 器 網(wǎng) 絡(luò) 中 ，每 個(gè) 節(jié) 點(diǎn) 可 以 通 過(guò) 某 種 測(cè) 距 技 術(shù) 獲 得 到 參 考 節(jié) 點(diǎn)的 距 離 。 （ AoA可 以 轉(zhuǎn) 化 為 多 邊 測(cè) 量 問(wèn) 題 ） 為 簡(jiǎn) 單 起 見(jiàn) ， 假 設(shè) 參 考 節(jié) 點(diǎn) 的 位 置 可 能 受 到 攻 擊 ，距 離 信 息 未 受 到 攻 擊 （ 只 有 測(cè) 量 誤 差 ） 。 在 （ x0,

32、y0） 的 未 知 節(jié) 點(diǎn) 收 到 N個(gè) 參 考 節(jié) 點(diǎn) 的 位 置及 相 應(yīng) 的 距 離 (x 1,y1,d1),(xN, yN, dN)， 未知 節(jié) 點(diǎn) 估 計(jì) 自 己 的 位 置 。 雙 邊 測(cè) 量 法 Bilateration 每 次 只 計(jì) 算 兩 個(gè) 方 程 ， 一 般 可 得 到 兩 個(gè) 實(shí) 數(shù) 解 。 Bilateration的 基 本 思 想 每 次 只 計(jì) 算 兩 個(gè) 方 程 ， 得 到 的 實(shí) 數(shù) 解 為 未 知 節(jié) 點(diǎn) 可 能的 位 置 ， 稱 候 選 位 置 。 如 果 不 存 在 攻 擊 和 噪 聲 ， 侯 選 位 置 中 應(yīng) 當(dāng) 會(huì) 有 一 些 重疊 的 點(diǎn) ，

33、這 個(gè) 點(diǎn) 便 是 未 知 節(jié) 點(diǎn) 的 位 置 。 當(dāng) 存 在 攻 擊 或 噪 聲 時(shí) ， 可 能 沒(méi) 有 重 合 點(diǎn) ， 但 是 在 誤 差范 圍 有 限 的 情 況 下 ， 由 正 常 樣 本 產(chǎn) 生 的 合 理 位 置 應(yīng) 當(dāng)分 布 在 真 實(shí) 位 置 的 附 近 ， 因 而 這 些 位 置 相 互 靠 近 。 Bilateration的 基 本 思 想 是 找 出 合 理 位 置 ， 并 只 利 用合 理 位 置 來(lái) 進(jìn) 行 位 置 估 計(jì) ， 方 法 是 找 出 最 大 的 侯 選 位置 簇 。 Bilateration的 算 法 過(guò) 程 未 知 節(jié) 點(diǎn) 對(duì) 于 獲 得 的 每 對(duì)

34、測(cè) 量 樣 本 計(jì) 算 候 選位 置 ， 得 到 包 含 M個(gè) 候 選 位 置 的 集 合 C。 對(duì) 于 C中 的 每 一 個(gè) 候 選 位 置 ci計(jì) 算 到 其 它 候選 位 置 的 距 離 ， 找 到 距 離 小 于 門(mén) 限 的 候 選位 置 ， 統(tǒng) 計(jì) 其 個(gè) 數(shù) ni， 并 記 錄 相 應(yīng) 的 候 選 位置 集 合 Ei。 找 到 ni中 的 最 大 值 nm， Em即 為 最 大 的 候選 位 置 簇 ， 計(jì) 算 這 些 位 置 的 質(zhì) 心 即 為 未 知 節(jié)點(diǎn) 的 位 置 。 Bilateration的 算 法 過(guò) 程 （ 續(xù) ） 更 精 確 一 些 ， 可 以 根 據(jù) Em找 到

35、 生 成 這 些 候 選位 置 的 參 考 節(jié) 點(diǎn) ， 賦 權(quán) 值 1， 棄 用 的 參 考 節(jié)點(diǎn) 賦 權(quán) 值 -1， 與 鄰 居 交 換 權(quán) 值 表 。 從 收 集 到 的 所 有 權(quán) 值 表 中 選 出 共 同 的 參 考 節(jié)點(diǎn) ， 將 它 們 的 權(quán) 值 相 加 ， 權(quán) 值 小 于 平 均 值 的參 考 節(jié) 點(diǎn) 棄 用 ， 將 其 生 成 的 侯 選 位 置 從 Em中刪 除 。 將 Em中 剩 余 的 候 選 位 置 求 平 均 ， 作 為 未 知 節(jié)點(diǎn) 的 位 置 估 計(jì) 。 及 測(cè) 距 誤 差 對(duì) 算 法 性 能 的 影 響 3. 傳 感 器 網(wǎng) 絡(luò) 中 的 射 頻 傳 播 模 型

36、 由 于 部 署 大 規(guī) 模 傳 感 器 網(wǎng) 絡(luò) 的 成 本 及 困 難 ， 目 前 大多 數(shù) 研 究 工 作 都 是 在 仿 真 環(huán) 境 中 進(jìn) 行 。 為 了 分 析 上 的 方 便 ， 研 究 人 員 常 使 用 一 些 理 想 的 模型 ， 但 理 想 模 型 與 實(shí) 際 情 況 是 否 相 符 一 直 受 到 質(zhì) 疑 。 傳 感 器 網(wǎng) 絡(luò) 中 受 質(zhì) 疑 最 多 的 一 個(gè) 模 型 是 射 頻 信 號(hào) 傳播 模 型 ， 認(rèn) 為 信 號(hào) 傳 播 是 各 向 同 性 的 。 該 模 型 直 接 導(dǎo) 致 了 圓 形 連 通 模 型 （ circular connectivity mode

37、l） ， 即 所 有 與 節(jié) 點(diǎn) O連 通 的 節(jié)點(diǎn) 均 位 于 以 O為 圓 心 、 通 信 距 離 為 半 徑 的 圓 中 。 3.1 大 規(guī) 模 傳 感 器 網(wǎng) 絡(luò) 的 復(fù) 雜 行 為 研 究 99的 研 究 表 明 ， 哪 怕 是 最 簡(jiǎn) 單 的 洪 泛 算 法也 會(huì) 導(dǎo) 致 圓 形 連 通 模 型 失 效 。9的 貢 獻(xiàn) 主 要 在 于 兩 個(gè) 方 面 ：l 建 立 了 一 個(gè) 實(shí) 際 的 較 大 規(guī) 模 密 集 傳 感 器 網(wǎng) 絡(luò) ， 從實(shí) 際 網(wǎng) 絡(luò) 中 獲 取 了 大 量 的 第 一 手 數(shù) 據(jù) ， 這 些 數(shù) 據(jù)表 明 應(yīng) 重 新 審 視 目 前 使 用 的 連 通 模 型

38、。l 第 一 次 系 統(tǒng) 分 析 了 影 響 算 法 全 局 行 為 的 因 素 。 研 究 例 子 -洪 泛 算 法 洪 泛 是 計(jì) 算 機(jī) 網(wǎng) 絡(luò) 中 實(shí) 現(xiàn) 最 簡(jiǎn) 單 、 使 用 最 廣 泛 和 研 究 最 充 分的 協(xié) 議 之 一 ， 主 要 用 于 數(shù) 據(jù) 的 分 發(fā) 。 洪 泛 是 許 多 復(fù) 雜 協(xié) 議 的 基 礎(chǔ) ， 在 大 規(guī) 模 傳 感 器 網(wǎng) 絡(luò) 中 更 是 頻繁 使 用 ， 如 發(fā) 現(xiàn) 路 由 、 傳 播 查 詢 請(qǐng) 求 、 發(fā) 布 網(wǎng) 絡(luò) 命 令 、 改 變網(wǎng) 絡(luò) 參 數(shù) 、 進(jìn) 行 多 跳 時(shí) 間 同 步 等 。 以 下 是 基 于 洪 泛 的 樹(shù) 構(gòu) 造 算 法

39、 ： 洪 泛 快 照 洪 泛 的 非 均 勻 性 測(cè) 度 實(shí) 驗(yàn) 平 臺(tái) 每 做 一 次 實(shí) 驗(yàn) 都 使 用 新 的 電 池 ； 所 有 節(jié) 點(diǎn) 的 天 線 長(zhǎng) 度 相 同 ， 且 具有 一 致 的 垂 直 方 向 ； 節(jié) 點(diǎn) 上 運(yùn) 行 TinyOS， 提 供 包 括物 理 層 糾 錯(cuò) 、 檢 錯(cuò) 、 MAC層 、網(wǎng) 絡(luò) 消 息 傳 輸 等 在 內(nèi) 的 完 整 協(xié) 議棧 ； MAC協(xié) 議 是 CSMA的 一 個(gè) 變 種 。Reno Mote 實(shí) 驗(yàn) 一 ： 理 解 鏈 路 特 性 將 169個(gè) 節(jié) 點(diǎn) 放 置 于 一 個(gè) 平 坦 、 開(kāi) 闊 的 停 車(chē) 場(chǎng) 上 ， 形成 13*13的 網(wǎng) 格

40、 網(wǎng) 絡(luò) ， 每 個(gè) 網(wǎng) 格 的 邊 長(zhǎng) 為 2英 尺 。 實(shí) 驗(yàn) 目 的 ： 繪 制 出 在 16個(gè) 射 頻 功 率 設(shè) 置 下 節(jié) 點(diǎn) 之 間 的連 通 特 性 。 基 站 控 制 節(jié) 點(diǎn) 的 發(fā) 送 ： 基 站 每 次 向 一 個(gè) 節(jié) 點(diǎn) 發(fā) 送 命 令 ，節(jié) 點(diǎn) 響 應(yīng) 基 站 的 命 令 發(fā) 送 。 在 每 個(gè) 功 率 設(shè) 置 下 ， 每 個(gè) 節(jié) 點(diǎn) 每 次 發(fā) 送 20個(gè) 包 ， 按 照100ms的 間 隔 依 次 發(fā) 送 。 接 收 節(jié) 點(diǎn) 記 錄 發(fā) 送 節(jié) 點(diǎn) ID、 包 序 號(hào) 和 發(fā) 送 功 率 （ 包 含在 包 的 載 荷 中 ） ， 保 存 在 自 己 的 存 儲(chǔ) 器

41、 中 。 利 用 這 些 數(shù) 據(jù) ， 繪 制 出 每 一 個(gè) 發(fā) 送 功 率 下 數(shù) 據(jù) 包 接 收的 統(tǒng) 計(jì) 圖 。 實(shí) 驗(yàn) 二 ： 研 究 洪 泛 的 行 為 將 156個(gè) 節(jié) 點(diǎn) 放 置 于 平 坦 、 開(kāi) 闊 的 停 車(chē) 場(chǎng) 上 ，形 成 13*12的 網(wǎng) 格 網(wǎng) 絡(luò) ， 每 個(gè) 網(wǎng) 格 的 邊 長(zhǎng) 為2英 尺 。 基 站 放 置 于 網(wǎng) 格 底 邊 的 中 點(diǎn) 。 基 站 周 期 性 地 啟 動(dòng) 洪 泛 傳 輸 過(guò) 程 ， 周 期 足 夠長(zhǎng) 以 確 保 前 一 次 洪 泛 已 結(jié) 束 ， 每 個(gè) 節(jié) 點(diǎn) 只 在第 一 次 收 到 一 個(gè) 新 消 息 時(shí) 轉(zhuǎn) 發(fā) 一 次 。 實(shí) 驗(yàn) 中

42、 共 設(shè) 置 了 8個(gè) 射 頻 功 率 ， 每 個(gè) 射 頻 功率 設(shè) 置 下 啟 動(dòng) 10次 不 重 疊 的 洪 泛 傳 輸 。 應(yīng) 用 層 和 MAC層 均 記 錄 必 要 的 信 息 ， 用 于實(shí) 驗(yàn) 結(jié) 束 后 重 建 消 息 的 傳 播 過(guò) 程 。 實(shí) 驗(yàn) 分 析 方 法 將 洪 泛 行 為 分 解 到 不 同 的 層 次 上 ， 在 每 一 層 上 使 用 不 同的 測(cè) 度 獨(dú) 立 地 研 究 這 些 行 為 ， 然 后 再 綜 合 這 些 分 析 來(lái) 解釋 全 局 行 為 。 在 鏈 路 層 上 ， 量 化 地 定 義 和 測(cè) 量 真 實(shí) 環(huán) 境 中 對(duì) 應(yīng) 于 給 定發(fā) 射 功

43、率 的 有 效 通 信 半 徑 ， 研 究 數(shù) 據(jù) 包 接 收 率 隨 傳 輸 距離 的 統(tǒng) 計(jì) 變 化 特 性 ， 確 定 哪 些 因 素 造 成 了 非 對(duì) 稱 性 。 在 MAC層 上 ， 使 用 時(shí) 間 信 息 來(lái) 給 出 描 述 洪 泛 傳 播 的 端到 端 特 性 和 本 地 特 性 （ 如 競(jìng) 爭(zhēng) 和 沖 突 ） 的 測(cè) 度 。 在 應(yīng) 用 層 上 ， 分 析 洪 泛 生 成 的 結(jié) 構(gòu) 。 綜 合 分 析 ： 重 建 消 息 傳 播 過(guò) 程 ， 解 釋 層 次 之 間 的 相 互 作用 如 何 導(dǎo) 致 最 終 的 全 局 行 為 。 （ 1） 鏈 路 層 分 析 包 接 收 率

44、 的 等 值 線 分 布 另 一 個(gè) 發(fā) 送 功 率 下 包 接 收 率 的 等 值 線 分 布 不 同 發(fā) 送 功 率 下 包 接 收 概 率 隨 距 離 的 分 布 連 通 半 徑 （ connectivity radius） 算 法 設(shè) 計(jì) 者 通 常 用 連 通 半 徑 及 圓 形 連 通 區(qū) 域 來(lái) 抽 象系 統(tǒng) ， 許 多 分 析 結(jié) 果 都 是 基 于 圓 形 區(qū) 域 ， 因 為 它 簡(jiǎn)化 了 分 析 ， 并 允 許 使 用 幾 何 方 法 。 9基 于 包 接 收 門(mén) 限 來(lái) 定 義 連 通 半 徑 ， 這 個(gè) 門(mén) 限 的選 擇 是 基 于 對(duì) 鏈 路 好 壞 的 判 斷 ：l

45、 稱 一 條 鏈 路 為 “ 好 ” 鏈 路 ， 如 果 可 以 使 用 前 向 糾 錯(cuò) 及 其它 技 術(shù) 來(lái) 使 包 吞 吐 率 達(dá) 到 一 個(gè) 恰 當(dāng) 的 水 平 。 l 稱 一 條 鏈 路 為 “ 壞 ” 鏈 路 ， 如 果 無(wú) 法 通 過(guò) 這 些 方 法 來(lái) 提高 包 吞 吐 率 。 基 于 這 個(gè) 標(biāo) 準(zhǔn) 和 上 圖 的 曲 線 ， 9將 “ 好 ” 鏈 路 的門(mén) 限 取 為 65%， “ 壞 ” 鏈 路 的 門(mén) 限 取 為 25%。 不 同 射 頻 發(fā) 送 功 率 下 的 連 通 半 徑 非 對(duì) 稱 鏈 路 9用 “ 好 ” 鏈 路 及 “ 壞 ” 鏈 路 的 概 念 來(lái) 定 義

46、非 對(duì) 稱 性 測(cè) 度 ：l 非 對(duì) 稱 鏈 路 ： 一 個(gè) 方 向 上 是 “ 好 ” 鏈 路 ， 另 一 個(gè) 方 向 上 是 “ 壞 ”鏈 路 。l 雙 向 鏈 路 ： 兩 個(gè) 方 向 上 均 是 “ 好 ” 鏈 路 。 （ 2） MAC層 分 析 9使 用 三 個(gè) 測(cè) 度 來(lái) 反 映 洪 泛 傳 輸 過(guò) 程 中 三 個(gè) 不 同 方 面的 問(wèn) 題 ：l 最 大 回 退 時(shí) 間 ： 反 映 每 個(gè) 節(jié) 點(diǎn) 通 信 區(qū) 域 內(nèi) 的 干 擾 （ 回 退 是競(jìng) 爭(zhēng) 的 結(jié) 果 ） 。l 接 收 延 遲 ： 網(wǎng) 絡(luò) 中 所 有 節(jié) 點(diǎn) 接 收 到 洪 泛 消 息 的 時(shí) 間 。l 結(jié) 束 時(shí) 間 ：

47、 網(wǎng) 絡(luò) 中 所 有 節(jié) 點(diǎn) 完 成 洪 泛 發(fā) 送 的 時(shí) 間 。 這 三 個(gè) 測(cè) 度 一 般 有 以 下 關(guān) 系 ： 三 個(gè) 測(cè) 度 的 實(shí) 驗(yàn) 數(shù) 據(jù) 最 大 回 退 時(shí) 間 隨 發(fā) 射 功 率 的 增 大 而 增 大 。 接 收 延 遲 與 結(jié) 束 時(shí) 間 的 差 異 也 隨 發(fā) 射 功 率 的 增 大而 增 大 。 沖 突 節(jié) 點(diǎn) 、 離 群 節(jié) 點(diǎn) 和 后 向 鏈 路 洪 泛 初 始 階 段 沖 突 頻 繁 ， 產(chǎn) 生 許 多 離 群 節(jié) 點(diǎn) ， 離 群 節(jié) 點(diǎn) 隨 后 接 收 消息 形 成 后 向 鏈 路 。 在 較 高 的 發(fā) 射 功 率 下 ， 節(jié) 點(diǎn) 具 有 較 大 的 通

48、 信 區(qū) 域 ， 沖 突 概 率 增 大 ，產(chǎn) 生 較 多 的 離 群 節(jié) 點(diǎn) ， 最 終 形 成 較 多 的 后 向 鏈 路 。 （ 3） 應(yīng) 用 層 分 析 節(jié) 點(diǎn) 層 次 ： 基 站 到 樹(shù) 上 某 個(gè) 節(jié) 點(diǎn) 的 跳 數(shù) 。 應(yīng) 用 層 分 析 （ 續(xù) ） 簇 大 小 ： 連 接 某 個(gè) 父 節(jié) 點(diǎn) 的 孩 子 節(jié) 點(diǎn) 個(gè) 數(shù) 。 （ 4） 總 結(jié) 論 文 提 出 了 四 種 值 得 注 意 的 影 響 ： 長(zhǎng) 鏈 路 、后 向 鏈 路 、 離 群 節(jié) 點(diǎn) 和 聚 集 。 離 群 節(jié) 點(diǎn) 可 以 用 MAC層 上 的 沖 突 解 釋 。 長(zhǎng) 鏈 路 可 以 用 傳 輸 的 方 向 性

49、解 釋 。 長(zhǎng) 鏈 路 導(dǎo) 致 某 個(gè) 方 向 的 洪 泛 傳 播 較 快 ， 反彈 回 來(lái) 填 充 傳 播 較 慢 的 區(qū) 域 或 存 在 離 群 節(jié)點(diǎn) 的 區(qū) 域 ， 形 成 后 向 鏈 路 。 應(yīng) 用 層 上 機(jī) 會(huì) 地 、 最 早 到 來(lái) 優(yōu) 先 的 父 節(jié) 點(diǎn)選 擇 算 法 導(dǎo) 致 高 度 聚 集 現(xiàn) 象 。 總 結(jié) （ 續(xù) ） 實(shí) 驗(yàn) 揭 示 了 鏈 路 層 上 幾 個(gè) 值 得 注 意 的 影 響 ： 高 度 不 規(guī)則 的 包 接 收 等 值 線 ， 傳 輸 的 方 向 性 導(dǎo) 致 長(zhǎng) 鏈 路 ， 長(zhǎng) 鏈路 呈 現(xiàn) 較 高 的 不 對(duì) 稱 性 等 。 有 些 影 響 可 以 用 現(xiàn)

50、 有 的 模 型 來(lái) 描 述 ， 但 有 些 影 響 無(wú) 法用 現(xiàn) 有 的 模 型 描 述 ， 其 對(duì) 協(xié) 議 行 為 的 影 響 也 沒(méi) 有 被 仿真 。 圓 形 模 型 或 概 率 模 型 對(duì) 于 充 分 理 解 復(fù) 雜 系 統(tǒng) 的 相 互 作用 是 不 充 分 的 。 非 對(duì) 稱 鏈 路 在 大 規(guī) 模 傳 感 器 網(wǎng) 絡(luò) 中 非 常 重 要 ， 一 個(gè) 健壯 的 協(xié) 議 必 須 能 夠 恰 當(dāng) 地 處 理 這 種 情 況 。 3.2 Radio Irregularity Model 10 節(jié) 點(diǎn) 的 接 收 信 號(hào) 強(qiáng) 度 表 示 為 ： 第 一 部 分 表 示 不 同 節(jié) 點(diǎn) 的 硬

51、 件 校 準(zhǔn) 和 電 源 狀 況 第 二 部 分 表 示 路 徑 損 耗 的 各 向 異 性 第 三 部 分 表 示 環(huán) 境 噪 聲 4. 傳 感 器 網(wǎng) 絡(luò) 中 的 數(shù) 據(jù) 管 理 在 傳 感 器 網(wǎng) 絡(luò) 中 ， 用 戶 感 興 趣 的 是 數(shù) 據(jù) 而 不 是 網(wǎng) 絡(luò) 本身 ， 因 此 數(shù) 據(jù) 管 理 （ 數(shù) 據(jù) 的 存 儲(chǔ) 與 訪 問(wèn) ） 是 傳 感 器 網(wǎng)絡(luò) 的 重 要 問(wèn) 題 。 在 IP風(fēng) 格 的 通 信 模 式 中 ， 通 過(guò) 節(jié) 點(diǎn) 地 址 來(lái) 訪 問(wèn) 數(shù) 據(jù) ；但 在 傳 感 器 網(wǎng) 絡(luò) 中 ， 通 過(guò) 節(jié) 點(diǎn) 標(biāo) 識(shí) 來(lái) 訪 問(wèn) 數(shù) 據(jù) 一 般 不可 行 ： l 用 戶 只

52、對(duì) 數(shù) 據(jù) 感 興 趣 ， 并 不 關(guān) 心 到 底 是 哪 個(gè) 節(jié) 點(diǎn) 采 集 了 這 個(gè)數(shù) 據(jù) ；l 在 隨 機(jī) 部 署 的 傳 感 器 網(wǎng) 絡(luò) 中 ， 節(jié) 點(diǎn) 標(biāo) 識(shí) 與 物 理 位 置 的 對(duì) 應(yīng) 關(guān)系 在 部 署 前 并 不 知 道 ， 在 部 署 后 獲 取 全 部 節(jié) 點(diǎn) 的 位 置 開(kāi) 銷(xiāo) 很大 ， 因 此 節(jié) 點(diǎn) 標(biāo) 識(shí) 對(duì) 于 數(shù) 據(jù) 訪 問(wèn) 的 用 處 不 大 。 傳 感 器 網(wǎng) 絡(luò) 中 的 數(shù) 據(jù) 訪 問(wèn) 模 式 用 戶 通 過(guò) 簡(jiǎn) 單 的 查 詢 語(yǔ) 句 請(qǐng) 求 所 需 要 的 信 息 ，比 如 “ 在 地 理 區(qū) 域 X中 觀 察 到 的 行 人 數(shù) 量 ” 。 匯

53、聚 節(jié) 點(diǎn) 通 過(guò) 分 析 查 詢 語(yǔ) 句 形 成 傳 感 器 網(wǎng) 絡(luò)中 的 查 詢 任 務(wù) ， 發(fā) 布 到 網(wǎng) 絡(luò) 中 。 符 合 條 件 的 傳 感 器 節(jié) 點(diǎn) （ 如 區(qū) 域 X中 的 節(jié) 點(diǎn) ）采 集 數(shù) 據(jù) ， 執(zhí) 行 行 人 檢 測(cè) 與 計(jì) 數(shù) 任 務(wù) ， 生 成事 件 報(bào) 告 。 事 件 報(bào) 告 發(fā) 送 給 匯 聚 節(jié) 點(diǎn) 。 需 要 解 決 的 問(wèn) 題 任 務(wù) 描 述 ： 如 何 描 述 用 戶 感 興 趣 的 數(shù) 據(jù) 任 務(wù) 擴(kuò) 散 ： 任 務(wù) 如 何 發(fā) 送 到 執(zhí) 行 該 任 務(wù) 的節(jié) 點(diǎn) 任 務(wù) 執(zhí) 行 ： 與 具 體 應(yīng) 用 有 關(guān) 數(shù) 據(jù) 獲 取 ： 數(shù) 據(jù) 如 何

54、 發(fā) 送 到 發(fā) 布 任 務(wù) 的 節(jié)點(diǎn) 4.1 定 向 擴(kuò) 散 （ directed diffusion） 12 應(yīng) 用 場(chǎng) 景 ：l 用 戶 通 過(guò) 長(zhǎng) 距 離 鏈 路 與 網(wǎng) 絡(luò) 中 的 匯 聚 節(jié) 點(diǎn) 連 接 ， 發(fā) 布 如下 任 務(wù) ： “ 在 接 下 來(lái) 的 T秒 時(shí) 間 內(nèi) ， 每 隔 I毫 秒 向 我 發(fā) 送出 現(xiàn) 在 子 區(qū) 域 R內(nèi) 的 任 何 四 足 動(dòng) 物 的 位 置 估 計(jì) ” 。 l 使 用 某 種 路 由 機(jī) 制 ， 該 任 務(wù) 被 傳 輸 到 位 于 子 區(qū) 域 R的 傳感 器 節(jié) 點(diǎn) 。l 該 區(qū) 域 的 每 個(gè) 節(jié) 點(diǎn) 采 集 數(shù) 據(jù) ， 執(zhí) 行 目 標(biāo) 檢

55、測(cè) 與 識(shí) 別 任 務(wù) 。若 檢 測(cè) 到 目 標(biāo) ， 每 隔 I毫 秒 生 成 一 個(gè) 事 件 描 述 。 l 事 件 消 息 發(fā) 送 到 匯 聚 節(jié) 點(diǎn) 。 （ 1） 任 務(wù) 描 述 （ 興 趣 ） 任 務(wù) 描 述 （ task descriptions） 用 一 系 列 描 述 任 務(wù)的 對(duì) 來(lái) 命 名 。 比 如 ， 動(dòng) 物 跟 蹤 任 務(wù) 可 以描 述 為 ： 直 觀 上 ， 任 務(wù) 描 述 指 出 了 對(duì) 匹 配 這 些 屬 性 的 數(shù) 據(jù) 的 興趣 ， 因 此 ， 將 這 樣 的 一 個(gè) 任 務(wù) 描 述 稱 為 一 個(gè) 興 趣（ interest） 。 數(shù) 據(jù) 命 名 為 響 應(yīng)

56、興 趣 而 發(fā) 送 的 數(shù) 據(jù) 也 用 類(lèi) 似 的 命 名 方 法 命 名 。比 如 ， 檢 測(cè) 到 動(dòng) 物 的 節(jié) 點(diǎn) 可 以 生 成 以 下 的 數(shù) 據(jù) ： 給 定 傳 感 器 網(wǎng) 絡(luò) 支 持 的 一 組 任 務(wù) ， 選 擇 一 種 命 名 方 案是 設(shè) 計(jì) 定 向 擴(kuò) 散 的 第 一 步 。 （ 2） 梯 度 興 趣 通 常 通 過(guò) 某 個(gè) 節(jié) 點(diǎn) （ sink） 注 入 網(wǎng) 絡(luò) ， 在duration指 定 的 時(shí) 間 之 后 ， 節(jié) 點(diǎn) 清 除 任 務(wù) 的 狀 態(tài) 。 對(duì) 于 每 個(gè) 活 躍 的 任 務(wù) ， 匯 聚 節(jié) 點(diǎn) 周 期 性 地 向 其 鄰 居 廣播 一 個(gè) 興 趣 。 初

57、 始 發(fā) 送 的 興 趣 中 ， interval屬 性 取 值 較 大 ， 主 要 用于 探 測(cè) 的 目 的 ， 如 ： 興 趣 緩 存 （ interest cache） 每 個(gè) 節(jié) 點(diǎn) 維 護(hù) 一 個(gè) 興 趣 緩 存 ， 每 一 項(xiàng) 對(duì) 應(yīng) 一 個(gè) 不 同 的 興 趣 。 每 個(gè) 興 趣 項(xiàng) 包 含 若 干 個(gè) 域 ， 如 ：l Timestamp： 最 近 一 次 收 到 興 趣 的 時(shí) 間l Gradient： 可 能 有 多 個(gè) ， 每 個(gè) 梯 度 域 對(duì) 應(yīng) 從 一 個(gè) 鄰 居 收 到 的 興 趣 ： Data rate： 取 自 興 趣 的 inverval屬 性 Durati

58、on： 取 自 興 趣 的 timestamp和 expiresAt屬 性 當(dāng) 節(jié) 點(diǎn) 收 到 一 個(gè) 興 趣 時(shí) ， 檢 查 緩 存 中 是 否 有 匹 配 的 項(xiàng) ：l 沒(méi) 有 匹 配 的 項(xiàng) ， 創(chuàng) 建 一 個(gè) 興 趣 項(xiàng) ， 梯 度 域 指 向 發(fā) 送 興 趣 的 鄰 居 節(jié) 點(diǎn) 。l 存 在 匹 配 的 興 趣 項(xiàng) ， 但 沒(méi) 有 指 向 發(fā) 送 節(jié) 點(diǎn) 的 梯 度 ， 添 加 一 個(gè) 梯 度 域 ，并 更 新 timestamp和 duration域 。l 存 在 匹 配 的 興 趣 項(xiàng) 及 梯 度 域 ， 則 只 是 更 新 timestamp和 duration域 。 當(dāng) 一

59、個(gè) 梯 度 過(guò) 期 時(shí) ， 將 其 從 興 趣 項(xiàng) 中 刪 除 ； 當(dāng) 一 個(gè) 興 趣 項(xiàng) 的 所 有 梯度 都 過(guò) 期 時(shí) ， 將 興 趣 項(xiàng) 從 緩 存 中 刪 除 。 興 趣 擴(kuò) 散 收 到 一 個(gè) 興 趣 后 ， 節(jié) 點(diǎn) 可 以 決 定 再 將 其 發(fā) 送 給 自 己的 一 些 鄰 居 進(jìn) 行 擴(kuò) 散 。 對(duì) 其 鄰 居 而 言 ， 這 個(gè) 興 趣 是從 該 節(jié) 點(diǎn) 發(fā) 出 的 （ 即 不 知 道 該 興 趣 的 真 正 sink） 。 節(jié) 點(diǎn) 如 果 最 近 已 經(jīng) 重 發(fā) 過(guò) 相 匹 配 的 興 趣 ， 也 可 以 不發(fā) 送 收 到 的 興 趣 。 一 般 有 好 幾 種 選 擇

60、鄰 居 的 方 法 ：l 轉(zhuǎn) 發(fā) 給 所 有 鄰 居 ， 相 當(dāng) 于 擴(kuò) 散 l 使 用 地 理 路 由 ， 只 將 興 趣 向 目 標(biāo) 區(qū) 域 擴(kuò) 散l 使 用 早 先 響 應(yīng) 其 它 興 趣 時(shí) 緩 存 的 數(shù) 據(jù) 通 過(guò) 興 趣 擴(kuò) 散 在 節(jié) 點(diǎn) 中 建 立 了 梯 度 ， 這 些 梯 度 形 成了 從 源 節(jié) 點(diǎn) 到 sink的 傳 輸 路 徑 。 興 趣 傳 播 與 梯 度 建 立 （ 3） 數(shù) 據(jù) 生 成 和 傳 播 rect區(qū) 域 內(nèi) 的 傳 感 器 節(jié) 點(diǎn) 使 用 相 同 的 方 法 處 理 興 趣 ， 除此 之 外 ， 指 令 本 地 傳 感 器 開(kāi) 始 采 集 數(shù) 據(jù) 和

61、 識(shí) 別 目 標(biāo) 。 檢 測(cè) 到 目 標(biāo) 的 傳 感 器 節(jié) 點(diǎn) 從 其 興 趣 緩 存 中 尋 找 匹 配 的 興趣 項(xiàng) 。 發(fā) 現(xiàn) 匹 配 的 興 趣 項(xiàng) 后 ， 按 照 所 有 梯 度 中 的 最 高 數(shù) 據(jù) 速 率生 成 事 件 樣 本 ， 單 播 發(fā) 送 給 每 個(gè) 梯 度 指 示 的 鄰 居 。 數(shù) 據(jù) 傳 播 接 收 到 數(shù) 據(jù) 消 息 的 節(jié) 點(diǎn) 從 其 興 趣 緩 存 中 尋 找 匹 配 的 興 趣項(xiàng) ：l 沒(méi) 有 找 到 相 匹 配 的 興 趣 項(xiàng) ， 丟 棄 數(shù) 據(jù) 消 息 ；l 找 到 匹 配 的 興 趣 項(xiàng) ， 檢 查 與 其 關(guān) 聯(lián) 的 數(shù) 據(jù) 緩 存 ： 緩 存

62、中 有 一 個(gè) 匹 配 的 緩 存 項(xiàng) ， 丟 棄 數(shù) 據(jù) 消 息 ； 否 則 ， 將 數(shù) 據(jù) 消 息 添 加 到 數(shù) 據(jù) 緩 存 中 ， 并 發(fā) 送 給 鄰 居 節(jié) 點(diǎn) ；根 據(jù) 數(shù) 據(jù) 緩 存 可 確 定 接 收 事 件 的 數(shù) 據(jù) 速 率 。 為 轉(zhuǎn) 發(fā) 數(shù) 據(jù) 消 息 ， 節(jié) 點(diǎn) 檢 查 興 趣 項(xiàng) 的 梯 度 列 表 ： l 如 果 所 有 梯 度 的 數(shù) 據(jù) 速 率 大 于 等 于 收 到 的 事 件 速 率 ， 直 接 將收 到 的 數(shù) 據(jù) 消 息 發(fā) 送 給 相 應(yīng) 的 鄰 居 ；l 如 果 某 些 梯 度 的 數(shù) 據(jù) 速 率 小 于 收 到 的 事 件 速 率 ， 降 頻 發(fā)

63、 送 。 （ 4） 路 徑 鞏 固 （ reinforcement） Sink收 到 低 速 率 事 件 后 ， 通 過(guò) 鞏 固 某 個(gè) 鄰 居 來(lái) 接 收 高 速 率 事 件 。 Sink利 用 數(shù) 據(jù) 驅(qū) 動(dòng) 的 本 地 規(guī) 則 選 擇 一 個(gè) 鄰 居 ， 向 其 發(fā) 送 具 有 較 小interval值 的 興 趣 。 如 果 新 的 數(shù) 據(jù) 速 率 高 于 鄰 居 節(jié) 點(diǎn) 相 應(yīng) 興 趣 項(xiàng) 中 任 何 一 個(gè) 梯 度 的 數(shù)據(jù) 速 率 ， 鄰 居 節(jié) 點(diǎn) 必 須 至 少 鞏 固 它 的 一 個(gè) 鄰 居 。 通 過(guò) 一 系 列 的 本 地 交 互 ， 建 立 起 一 條 從 源 節(jié) 點(diǎn)

64、 到 sink節(jié) 點(diǎn) 的 高 事件 速 率 傳 輸 路 徑 。 利 用 數(shù) 據(jù) 緩 存 和 數(shù) 據(jù) 驅(qū) 動(dòng) 的 本 地 規(guī) 則 選 擇 鞏 固 的 鄰 居 節(jié) 點(diǎn) ， 如 ： l 第 一 個(gè) 發(fā) 來(lái) 最 新 匹 配 事 件 的 鄰 居l 發(fā) 來(lái) 最 新 匹 配 事 件 的 所 有 鄰 居l 發(fā) 來(lái) 最 多 事 件 的 鄰 居l 一 向 較 早 發(fā) 送 事 件 的 鄰 居 路 徑 鞏 固 取 消 鞏 固 （ negatively reinforcement） 以 上 算 法 可 能 導(dǎo) 致 多 條 路 徑 被 鞏 固 ， 如 果 某 條 路 徑 一直 較 差 ， 需 要 一 個(gè) 機(jī) 制 來(lái) 取

65、消 對(duì) 路 徑 的 鞏 固 。 取 消 鞏 固 的 方 法 ：l 超 時(shí) ： 所 有 高 事 件 速 率 的 梯 度 必 須 被 顯 式 地 鞏 固 ， 否 則 在 規(guī)定 的 時(shí) 間 后 被 取 消 鞏 固 。 l 顯 式 降 級(jí) ： 通 過(guò) 發(fā) 送 低 數(shù) 據(jù) 速 率 的 興 趣 來(lái) 顯 式 取 消 對(duì) 某 個(gè) 鄰居 節(jié) 點(diǎn) 的 鞏 固 。 如 果 某 個(gè) 興 趣 項(xiàng) 的 所 有 梯 度 均 為 低 數(shù) 據(jù) 速 率 ， 節(jié) 點(diǎn) 取消 鞏 固 那 些 向 其 發(fā) 送 高 速 率 事 件 的 鄰 居 。 選 擇 哪 個(gè) 鄰 居 節(jié) 點(diǎn) 取 消 鞏 固 ？ l 沒(méi) 有 新 事 件 到 來(lái) 的 鄰

66、居l 較 少 發(fā) 送 新 事 件 的 鄰 居l （ 5） 定 向 擴(kuò) 散 的 特 色 以 數(shù) 據(jù) 為 中 心 ， 所 有 通 信 使 用 興 趣 來(lái) 描 述 數(shù) 據(jù) 。 在 擴(kuò) 散 過(guò) 程 中 為 事 件 報(bào) 告 建 立 多 條 傳 輸 路 徑 ，然 后 基 于 觀 察 到 的 路 徑 性 能 ， 使 用 路 徑 鞏 固 來(lái)減 少 路 徑 ， 只 保 留 少 數(shù) 較 好 的 路 徑 。 使 用 數(shù) 據(jù) 緩 存 來(lái) 避 免 回 路 發(fā) 生 ， 定 向 擴(kuò) 散 及 路徑 鞏 固 不 保 證 無(wú) 環(huán) 路 由 。 4.2 傳 感 器 網(wǎng) 絡(luò) 中 的 數(shù) 據(jù) 存 儲(chǔ) 策 略 13 傳 感 器 網(wǎng) 絡(luò) 中 的 數(shù) 據(jù) 存 儲(chǔ) 研 究 節(jié) 點(diǎn) 采 集 的 數(shù)據(jù) 在 網(wǎng) 絡(luò) 中 的 存 儲(chǔ) 策 略 ：l 如 何 將 數(shù) 據(jù) 存 放 到 網(wǎng) 絡(luò) 中 合 適 的 位 置l 查 詢 請(qǐng) 求 如 何 路 由 到 存 儲(chǔ) 位 置 信 息 中 介 （ information brokerage） ：l 生 產(chǎn) 者 （ 傳 感 器 節(jié) 點(diǎn) ） 將 產(chǎn) 生 的 數(shù) 據(jù) 按 照 某 種 策略 存 放 在 特 定 的 位