【正文】 中科院計(jì)算所 授課教師：魯士文 1 中科院計(jì)算所網(wǎng)絡(luò)課程 10自組織移動(dòng)網(wǎng)絡(luò) IntraEtherInter中科院計(jì)算所 授課教師：魯士文 2 第十單元 自組織移動(dòng)網(wǎng)絡(luò) 什么是 ad hoc無線網(wǎng)絡(luò)？ Ad hoc移動(dòng)網(wǎng)絡(luò)面臨的挑戰(zhàn) Ad hoc無線介質(zhì)訪問協(xié)議 MACABI協(xié)議 PAMAS協(xié)議 DBTMA協(xié)議 MARCH協(xié)議 Ad hoc按需距離向量路由選擇 基于關(guān)聯(lián)的長(zhǎng)活路由選擇 中科院計(jì)算所 授課教師：魯士文 3 什么是 ad hoc無線網(wǎng)絡(luò)？ ? Ad hoc無線網(wǎng)絡(luò) 是一個(gè)有兩個(gè)或更多個(gè)具有無線通信和網(wǎng)絡(luò)連接能力的設(shè)備的集合。這些設(shè)備都可以跟在它們的無線范圍內(nèi)的另一個(gè)節(jié)點(diǎn)直接通信 ，或者也可以跟它們的無線范圍之外的節(jié)點(diǎn)通信。在后者的情況下使用一個(gè)中間節(jié)點(diǎn)把分組從源向著目的地 中繼或轉(zhuǎn)發(fā) 。 ? Ad hoc網(wǎng)絡(luò)是 自組織 的和 自適應(yīng)的 。這就意味著所形成的網(wǎng)絡(luò)可以 動(dòng)態(tài)地重構(gòu) 而不需要任何系統(tǒng)管理。術(shù)語“ Ad hoc” 意味著“ 可以取不同的形式 ”，并且“ 可以是移動(dòng)的、獨(dú)立的或連網(wǎng)的 ”。 Ad hoc節(jié)點(diǎn)或設(shè)備應(yīng)該能夠檢測(cè)到其它同類設(shè)備的存在，并執(zhí)行必要的握手過程，以便允許通信和共享信息和服務(wù)。 中科院計(jì)算所 授課教師：魯士文 4 什么是 ad hoc無線網(wǎng)絡(luò)？ ? 由于 Ad hoc無線設(shè)備可以取不同的形式，例如掌上電腦、筆記本和因特網(wǎng)電話等， 設(shè)備 的計(jì)算、存儲(chǔ)和通信能力可能 差別很大 。 Ad hoc設(shè)備應(yīng)該不但能夠發(fā)現(xiàn)跟鄰接設(shè)備或節(jié)點(diǎn)的連接性的存在，而且能夠識(shí)別這些設(shè)備的類型以及它們對(duì)應(yīng)的屬性。由于一個(gè) Ad hoc無線網(wǎng)絡(luò) 不依賴任何固定的網(wǎng)絡(luò)實(shí)體 ，它本身基本上就是一個(gè) 無基礎(chǔ)的網(wǎng)絡(luò) 。不必有固定的基站，沒有導(dǎo)線，也 沒有固定的路由器 。然而，由于存在移動(dòng)性， 必須交換路由信息以反映鏈路連接性的變化。 ? Ad hoc移動(dòng)設(shè)備的多樣性還意味著它們的 電池容量的差別 。由于 Ad hoc網(wǎng)絡(luò)的節(jié)點(diǎn)需要對(duì)由其它節(jié)點(diǎn)發(fā)送的數(shù)據(jù)分組進(jìn)行轉(zhuǎn)發(fā)， 功耗 就成了關(guān)鍵的問題。 中科院計(jì)算所 授課教師：魯士文 5 什么是 ad hoc無線網(wǎng)絡(luò)？ ? 一個(gè) Ad hoc移動(dòng)設(shè)備 作為服務(wù)器或服務(wù)提供者的能力 跟它的計(jì)算能力、內(nèi)存和外存容量以及電池壽命有關(guān)。這就意味著在網(wǎng)絡(luò)中的一些設(shè)備比其它設(shè)備功能強(qiáng)；一些設(shè)備可以是服務(wù)器，其它設(shè)備只能是客戶機(jī)。此外，為其它節(jié)點(diǎn) 中繼分組會(huì)消耗自己的能量 ，因此，一個(gè)移動(dòng)節(jié)點(diǎn)在承諾為其它節(jié)點(diǎn)轉(zhuǎn)發(fā)分組之前應(yīng)該考慮自己的生存條件。 ? 無線傳感器網(wǎng)絡(luò) 是一種形式的 Ad hoc無線網(wǎng)絡(luò)。傳感器通過無線連接，它們?cè)谶m當(dāng)?shù)臅r(shí)候把 信息中繼 到某些選定的節(jié)點(diǎn)。這些選定的節(jié)點(diǎn)再執(zhí)行一些基于所收集的數(shù)據(jù)的計(jì)算（通過一個(gè)通常稱作 數(shù)據(jù)融合 的進(jìn)程），從而得到 最終的統(tǒng)計(jì)數(shù)據(jù) （它們反映出對(duì)環(huán)境和戰(zhàn)術(shù)條件的評(píng)估），允許做出 關(guān)鍵的決策 。 中科院計(jì)算所 授課教師：魯士文 6 什么是 ad hoc無線網(wǎng)絡(luò)？ ? 有 多種多樣的傳感器 ，包括聲的、地震的、圖像的、熱能的、方位的和溫度傳感器。這些傳感器的建立需要高度 集成的電子學(xué) ，比如微電子機(jī)械系統(tǒng) MEMS。這些無線傳感器網(wǎng)絡(luò)的實(shí)現(xiàn)面臨著一系列的 挑戰(zhàn) ，主要包括： (a)設(shè)備制造； (b)電源生命保持； (c)能量高效利用的協(xié)議； (d)分布式計(jì)算； (e)規(guī)?？缮煺剐?； (f)數(shù)據(jù)傳播通路的產(chǎn)生； (g)安全性。 中科院計(jì)算所 授課教師：魯士文 7 什么是 ad hoc無線網(wǎng)絡(luò)？ ? 無線傳感器網(wǎng)絡(luò)的設(shè)計(jì)面向 低的數(shù)據(jù)吞吐率 （一般不超過 512位 /秒，可以低到 1位 /秒或更低）、 大的報(bào)文延遲 （數(shù)秒甚至數(shù)分鐘的延遲都是可以接受的，通常禁止傳送視頻和音頻數(shù)據(jù)）、 低成本 、 低功耗 和 自組織的拓?fù)浣Y(jié)構(gòu) 。它的許多 應(yīng)用都不需要移動(dòng)性 。為了降低網(wǎng)絡(luò)設(shè)備的成本，安全特征 必須能夠用廉價(jià)的硬件實(shí)現(xiàn)。低的邏輯門數(shù)量、受限的存儲(chǔ)器容量和少的可執(zhí)行指令的條數(shù)限制了可以采用的安全算法的類型。無線傳感器網(wǎng)絡(luò)還有一些其他方面的需求，包括網(wǎng)絡(luò) 規(guī)?？蓴U(kuò)展性 （設(shè)備輕小，但數(shù)量可能很大，如倉(cāng)庫(kù)或超市的物品傳感部件）、標(biāo)準(zhǔn)化引導(dǎo)的規(guī)模生產(chǎn) 、 容錯(cuò) 以及對(duì)各種 惡劣環(huán)境 的適應(yīng)性。 ? 一個(gè)無線 ad hoc傳感器網(wǎng)絡(luò) 用較低的數(shù)據(jù)吞吐率和較大的報(bào)文延遲換取較低的成本和較少的電源功耗 。主要目標(biāo)是設(shè)計(jì)滿足需求的 物理層、數(shù)據(jù)鏈路層和網(wǎng)絡(luò)層 的通信協(xié)議。 中科院計(jì)算所 授課教師：魯士文 8 什么是 ad hoc無線網(wǎng)絡(luò)？ ? 無線 ad hoc傳感器網(wǎng)絡(luò)的設(shè)備可以是 固定的、可攜帶的和移動(dòng)的 ，網(wǎng)絡(luò)提供 低數(shù)據(jù)速率的無線連接 。 位置感知性 被認(rèn)為是它的頗具特色的能力。 ? 無線 ad hoc傳感器網(wǎng)絡(luò)的典型應(yīng)用有 庫(kù)存管理 、 工業(yè)監(jiān)控 、 保安系統(tǒng) 、智能農(nóng)業(yè) 以及 家庭消費(fèi)電子產(chǎn)品 。無線傳感器節(jié)點(diǎn)將被放置在天花板上、工礦企業(yè)的設(shè)備里、農(nóng)場(chǎng)中、戰(zhàn)場(chǎng)上以及家用電器內(nèi)等地方。它們以最少的人工干預(yù)執(zhí)行 物體定位 、 危險(xiǎn)感知 和 環(huán)境監(jiān)控 等功能。成功的關(guān)鍵是提供輕小的低成本的節(jié)點(diǎn)，更重要地，節(jié)點(diǎn)必須只消耗超低的功率，以避免頻繁的電池更換。 ? 我們?cè)诒締卧?重點(diǎn)討論無線移動(dòng) ad hoc 網(wǎng)絡(luò) 。 中科院計(jì)算所 授課教師：魯士文 9 什么是 ad hoc無線網(wǎng)絡(luò)？ ? 在一個(gè) Ad hoc移動(dòng)網(wǎng)絡(luò)中的移動(dòng)主機(jī)可以跟它的直接對(duì)等方通信，即僅限于 單個(gè)無線跳段 。然而如果有 3個(gè)或更多個(gè)節(jié)點(diǎn)都在可通信的范圍內(nèi)（但互相不必是單個(gè)跳段的路程），那么就是 遠(yuǎn)程到遠(yuǎn)程 的移動(dòng)節(jié)點(diǎn)通信。在典型的情況下，遠(yuǎn)程到遠(yuǎn)程通信跟 成組遷移 有關(guān)。不同類型的 Ad hoc通信產(chǎn)生不同的交通特征。 ? 一個(gè) Ad hoc路由包含源（ SRC）、目的地（ DEST）和可能的若干個(gè)中間節(jié)點(diǎn)（ IN）。這些節(jié)點(diǎn)中任意一個(gè)的 移動(dòng) 都可能 影響路由 的有效性。路由中的 源節(jié)點(diǎn)有一個(gè)下行鏈路 ，當(dāng)它移動(dòng)出下行鄰居的無線覆蓋范圍的時(shí)候，現(xiàn)有的路由會(huì)立即變得無效。因此，所有的下游節(jié)點(diǎn)必須得到通知，它們才可能刪除它們的無效路由表項(xiàng)。同樣地，當(dāng)一個(gè) 目的地節(jié)點(diǎn)移動(dòng)出它的上游鄰居的無線覆蓋范圍 的時(shí)候，該路由也將變得無效。在這里，上游節(jié)點(diǎn)必須得到通知，它們才能夠刪除它們的無效路由表項(xiàng)。最后，一個(gè)支持現(xiàn)有路由的 中間節(jié)點(diǎn)的移動(dòng) 也可能使得該路由變得無效。 中科院計(jì)算所 授課教師：魯士文 10 什么是 ad hoc無線網(wǎng)絡(luò)？ ? 所有這些移動(dòng)都使得許多常規(guī)的分布式路由協(xié)議對(duì)鏈路變化做出響應(yīng)，其結(jié)果是更新網(wǎng)絡(luò)內(nèi)所有的其余節(jié)點(diǎn)，以保持路由信息的一致性。然而，更新過程涉及在無線介質(zhì)上的廣播，引起帶寬浪費(fèi)和總的網(wǎng)絡(luò)控制交通的增加。因此， Ad hoc網(wǎng)絡(luò)需要新的路由協(xié)議 。 ? 除了上述移動(dòng)類型之外，在兩個(gè)移動(dòng)子網(wǎng)之間的執(zhí)行子網(wǎng) 橋接功能的節(jié)點(diǎn)的移動(dòng)可能把移動(dòng) 子網(wǎng)分割 成更小的子網(wǎng)。一個(gè)移動(dòng)子網(wǎng)的性質(zhì)說明，如果源和目的節(jié)點(diǎn)都是該子網(wǎng)的成分，那么應(yīng)該存在一條或多條路由，除非該子網(wǎng)被某個(gè)子網(wǎng) 橋接移動(dòng)節(jié)點(diǎn)分區(qū)了。另一方面，某些節(jié)點(diǎn)的移動(dòng)可能引起 子網(wǎng)的合并 ，形成更大的子網(wǎng)。 中科院計(jì)算所 授課教師：魯士文 11 什么是 ad hoc無線網(wǎng)絡(luò)？ ? 當(dāng)移動(dòng)子網(wǎng)合并形成更大的子網(wǎng)時(shí)，路由算法可以通過更新所有節(jié)點(diǎn)的路由表來接受新的子網(wǎng)。然而，這是非常低效的。有效的路由機(jī)制應(yīng)該放棄這一過程，并且選擇 只更新受到影響的節(jié)點(diǎn)的相關(guān)路由表 ，這已是移動(dòng)節(jié)點(diǎn)的無線 數(shù)據(jù)鏈路層功能 的一個(gè)固有的部分。 ? 從應(yīng)用的角度看問題，可以使用移動(dòng)子網(wǎng)支持 漫游合作計(jì)算 。當(dāng)兩個(gè)合作組聚和，或者當(dāng)新的用戶通過進(jìn)入無線范圍加入時(shí)，合作成員在規(guī)模上可能增大。 ? 在現(xiàn)實(shí)中，可能存在源、目的地和中間節(jié)點(diǎn)的 并發(fā)移動(dòng) ，因此在調(diào)用多重的路由重構(gòu)或修正過程時(shí)，需要有一些規(guī)則來 保證一致性 。如果所執(zhí)行的路由重構(gòu)是適當(dāng)?shù)?，這些過程最終應(yīng)該 收斂 。 中科院計(jì)算所 授課教師：魯士文 12 Ad hoc移動(dòng)網(wǎng)絡(luò)面臨的挑戰(zhàn) ? 大多數(shù)的實(shí)驗(yàn) Ad hoc網(wǎng)絡(luò)是 基于 ISM頻段 。為了防止干擾，Ad hoc網(wǎng)絡(luò)必須在某些允許的或指定的頻譜范圍上運(yùn)行。大多數(shù)微波爐運(yùn)行在 ，因此可能會(huì)干擾無線 LAN系統(tǒng)。頻譜不僅被嚴(yán)格地控制和分配，而且也需要購(gòu)買?？梢詣?dòng)態(tài)建立和拆除的 Ad hoc網(wǎng)絡(luò)，還不清楚誰應(yīng)該為這個(gè)頻譜付費(fèi)。 ? 跟蜂窩網(wǎng)絡(luò)不同， 在 Ad hoc無線網(wǎng)絡(luò)中沒有中心控制和全局同步 。因此， TDMA和 FDMA機(jī)制在這里不適用 。此外，現(xiàn)有的許多 MAC協(xié)議都不處理主機(jī)移動(dòng)性。這樣，為了支持QoS，對(duì)于幀的調(diào)度和即時(shí)發(fā)送是困難的。 中科院計(jì)算所 授課教師：魯士文 13 Ad hoc移動(dòng)網(wǎng)絡(luò)面臨的挑戰(zhàn) ? 在一個(gè) Ad hoc無線網(wǎng)絡(luò)中，由于同一個(gè)介質(zhì)被多個(gè)移動(dòng) Ad hoc節(jié)點(diǎn)共享，對(duì)于該 共享通道的訪問必須通過一種 MAC協(xié)議以分布式的方式進(jìn)行 。在沒有靜態(tài)節(jié)點(diǎn)的情況下，各個(gè)節(jié)點(diǎn)不能夠依賴一個(gè)中心的協(xié)調(diào)進(jìn)程。MAC協(xié)議必須競(jìng)爭(zhēng)對(duì)共享通道的訪問 ，同時(shí)要避免跟鄰居節(jié)點(diǎn)的可能的沖突。在為 Ad hoc無線網(wǎng)絡(luò)設(shè)計(jì) MAC協(xié)議的時(shí)候，必須考