基于無線移動的Ad Hoc網格研究

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

1 Ad Hoc網絡概述[1][2]

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

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

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

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

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

2 AdHoc網格概念[3]

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

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

3 任務調度算法[2]

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

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

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

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

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

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

圖1 DAG圖

圖2 makespan實驗數據比較圖

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

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

5 結束語

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