基于無線移動的Ad Hoc網(wǎng)格研究

黑龍江工業(yè)學院電氣與信息工程系 張 妍 劉 鋒 郭維威

1 Ad Hoc網(wǎng)絡概述[1][2]

2018年1月31日中國互聯(lián)網(wǎng)絡信息中心關于《中國互聯(lián)網(wǎng)絡發(fā)展統(tǒng)計報告》顯示：截止到2017年12月，中國網(wǎng)民規(guī)模達到7.72億，普及率達到55.8%，超過全球平均水平4.1個百分點，超過亞洲平均水平9.1個百分點，全年新增網(wǎng)民4074萬，增長率為5.6%，手機網(wǎng)民規(guī)模達到7.53億。由此可見人們的學習、工作、生活等方方面面越來越多地依賴于無線網(wǎng)絡，對無線網(wǎng)絡信號質(zhì)量和速度的要求也越來越高。目前，大部分移動通信網(wǎng)絡還是建立在固定基站等有線基礎設施基礎上的，為了在無固定基站的特殊環(huán)境下有效通信，1991年IEEE802.11標準委員會運用"Ad hoc網(wǎng)絡"來描述具有特殊自組織對等式多跳移動通信網(wǎng)絡，Ad Hoc網(wǎng)絡技術正式誕生了。

Ad Hoc源自于拉丁語，是"for this"的意思，通常引申為"for this purpose only"，可以理解成Ad Hoc網(wǎng)絡是一種有特殊用途的網(wǎng)絡，也被稱為Multi Hop Wireless Network、或者Self Organized Network、或者Infrastructureless Network。Ad Hoc網(wǎng)絡的前身是Packet Radio Network，主要針對軍事領域通信的需要而研究的，已經(jīng)持續(xù)發(fā)展了近40年。

Ad Hoc網(wǎng)絡是由一組帶有自動收發(fā)功能和路由選擇功能的移動終端組成，網(wǎng)絡通信過程中所有節(jié)點的地位相同，除了具有普通移動終端功能外，還具有報文轉發(fā)功能，節(jié)點與節(jié)點中間的通信聯(lián)系可以由其他多個節(jié)點參與進來（也被稱為多跳），通過分層網(wǎng)絡協(xié)議和分布式算法，構成任意的網(wǎng)絡拓撲，實現(xiàn)了網(wǎng)絡的獨立工作。

Ad Hoc網(wǎng)絡既具備計算機網(wǎng)絡的特點又具備移動通信的特點，例如無中心特性：Ad hoc網(wǎng)絡中沒有絕對意義上的控制中心，每一個節(jié)點的地位一樣，并且各個節(jié)點可以任意地隨時加入進來或隨時選擇離開；自組織特性：無需基礎硬件設施的支持，在任何地方、任何時間組建獨立通信網(wǎng)絡；動態(tài)的網(wǎng)絡拓撲特性：由于移動終端的個數(shù)、速度和位置可以任意改變，網(wǎng)絡拓撲也隨時發(fā)生變化。

Ad Hoc網(wǎng)絡自身自動快速組網(wǎng)的能力和設備相對低廉的價格提供了廣泛的應用價值，例如：軍事領域的應用：Ad Hoc網(wǎng)絡主要應用在軍事領域，適合車載、單兵、指揮所等場所，是數(shù)字化戰(zhàn)場的核心技術，可以大大提高軍隊的戰(zhàn)備水平；搶險救災領域的應用：當發(fā)生自然災害后，原有的通信設施可能被摧毀，而緊急救援工作需要立即展開，因其無需架設硬件網(wǎng)絡設施而能夠快速展開工作的Ad Hoc網(wǎng)絡非常適合在這樣惡劣的環(huán)境下提供通信保障；團隊通信領域：不僅適用于手機、PDA、筆記本等電子設備之間的通信，還適用于會議、慶典、虛擬教室、移動醫(yī)療系統(tǒng)等臨時場所的通信。

2 AdHoc網(wǎng)格概念[3]

網(wǎng)格（Grid）是一種剛剛興起的技術，能夠?qū)⒕W(wǎng)絡上的計算資源、數(shù)據(jù)資源、存儲資源和信息資源等各種豐富資源有機地組合在一起，按照某種規(guī)則有序地協(xié)同工作，充分實現(xiàn)資源共享，為廣大網(wǎng)絡用戶服務，可以應用在科研領域、生物領域、教育領域、醫(yī)療領域、航空航天領域等等，標志著計算領域進入了高性能階段。

為了適應不斷變化的網(wǎng)絡環(huán)境、動態(tài)的網(wǎng)格參與、自組快速的移動連接而提出的移動通信與網(wǎng)格有機結合起來形成的Ad Hoe網(wǎng)格，透明、安全、無縫、有效地支持移動用戶和資源，非常適用于現(xiàn)階段大量涌現(xiàn)的低功耗存儲移動設備。Ad Hoe網(wǎng)格是一種異構可移動的無固定結構的通信和計算系統(tǒng)，獲得安全、高效的網(wǎng)絡服務，廣泛應用于軍事領域、商用領域和民用領域。

3 任務調(diào)度算法[2]

Ad Hoe網(wǎng)格是無線技術和網(wǎng)格計算的融合，資源管理和任務調(diào)度是它的兩個重要組成部分。資源管理是根據(jù)用戶請求，找到合適資源，但資源發(fā)現(xiàn)的查全率和效率直接影響后面的調(diào)度問題【4】；任務調(diào)度是滿足用戶需求和優(yōu)先約束關系為前提，根據(jù)相應的分配策略將下一步執(zhí)行的任務確定出執(zhí)行順序，并合理地分配到各節(jié)點上有序地執(zhí)行，達到總體執(zhí)行時間(makespan)最短的效果。Ad Hoe網(wǎng)格拓撲頻繁變化、資源豐富，合理高效的調(diào)度算法不但可以提高資源的利用率，還可以減少任務的總體執(zhí)行時間。

概況地說，Ad Hoe網(wǎng)格調(diào)度算法以提高網(wǎng)格總體效率為目的，根據(jù)用戶需求和網(wǎng)格即時資源情況而完成最優(yōu)化調(diào)度。其實調(diào)度問題就是NP-完成問題，國內(nèi)外的研究學者提出了許多不同的算法，根據(jù)算法不同的基本思想，調(diào)度算法的分類方式有很多，典型的分類方式有：靜態(tài)調(diào)度算法、動態(tài)調(diào)度算法和混合調(diào)度算法（靜態(tài)調(diào)度算法和動態(tài)調(diào)度算法結合在一起使用）。

OLB隨機負載均衡算法：是靜態(tài)調(diào)度算法中最簡單的一種，不考慮執(zhí)行時間隨機將某個任務分配給某資源。優(yōu)點是算法簡單、易實現(xiàn)，缺點是利用該調(diào)度算法可能會得到一個比較差的makespan。

Min-Min算法：是動態(tài)調(diào)度算法的一種，主要完成獨立任務調(diào)度問題，該算法的思想是將盡可能多的把任務分配給用時最短的設備上，所以算法自身執(zhí)行時間短，具有很好的makespan，許多典型的DAG建模都是建立在Min-Min算法基礎上的。

GS算法：是動態(tài)調(diào)度算法的一種，主要完成異構分布計算系統(tǒng)的任務調(diào)度問題，將整體任務轉換成若干個子任務集合，根據(jù)依賴性逐步地找出互不相干的子任務進行調(diào)度，直到所以子任務調(diào)度完成。過濾的次數(shù)直接決定了makespan，因此減少過濾的次數(shù)有利于改進調(diào)度算法，該算法具有簡單、易實現(xiàn)的特點。

評價調(diào)度系統(tǒng)的兩個基本指標是調(diào)度質(zhì)量和調(diào)度算法效率，調(diào)度質(zhì)量是指優(yōu)化調(diào)度的性能，調(diào)度算法效率是指任務完成時間的復雜性。對于一個整體任務來說，通過優(yōu)化調(diào)度以后用時越短越好，而如果多個調(diào)度算法完成相同的調(diào)度質(zhì)量，那么調(diào)度算法越簡單越好。

圖1 DAG圖

圖2 makespan實驗數(shù)據(jù)比較圖

4 實例模型分析[2][4]

在一個臨時場所舉辦會議，假設臨時用筆記本電腦、智能手機和PDA組建一個移動網(wǎng)格來協(xié)助會議的順利召開。模擬實驗在Windows 2017環(huán)境下運行，利用隨機生成算法產(chǎn)生DAG圖，如圖1所示，設定參數(shù)后列出EEC矩陣和ETC矩陣，對模擬任務集進行OLB算法和GS算法，分別比較α在0、0.2、0.4、0.6、0.8、1情況下的數(shù)據(jù)實驗，實驗60次，結果取平均值，實驗makespan的比較結果如圖2所示。

5 結束語

隨著人們擺脫有線網(wǎng)絡的束縛，對無線網(wǎng)絡要求的提升，使得移動計算技術、網(wǎng)格技術、無線技術與數(shù)據(jù)庫技術融合得更加緊密，因此，對Ad Hoc網(wǎng)格技術的研究具有重要的社會意義和經(jīng)濟價值。