[發明專利]移動計算環境中面向混合廣播的多數據項廣播調度方法

無效

• 申請號: 201210387130.6
• 申請日: 2012-10-12
• 公開（公告）號: CN102857875A
• 公開（公告）日: 2013-01-02
• 發明（設計）人: 車曉波;李研強;閆旭琴;毛成勇
• 申請（專利權）人: 山東省科學院自動化研究所
• 主分類號: H04W4/06
• 分類號: H04W4/06;H04W72/12
• 代理公司: 濟南圣達知識產權代理有限公司 37221
• 代理人: 王吉勇

技術領域

本發明涉及一種無線移動計算技術，尤其是一種移動計算環境中面向混合廣播的多數據項廣播調度方法。

背景技術

目前，隨著無線通信網絡的發展，數字無線通信已經被廣泛應用，與傳統的分布式計算環境相比，移動計算環境中的無線通信具有帶寬小，通信質量差，上行與下行通信開銷非對稱性明顯等特點。針對這些特性，人們提出了“數據廣播”這一新的數據傳送模式，通過向空中廣播數據，用戶只需要接收自己感興趣的數據即可，減少了上行開銷，并且系統中移動設備數量的增加對服務器方面影響很小，可以支持大量移動設備并發訪問服務器上的數據。對于數據廣播技術研究而言，選擇什么樣的數據廣播和如何進行廣播是兩個重要的課題，在移動計算環境中，很多應用活動具有較強的時效性，要求在規定的時刻或者一定的時間內完成處理，否則新的數據對當前用戶的決策或者指導失去意義，比如駛入某路段的車輛請求該路段的路況信息，對其有積極的指導作用，一旦駛出該路段后，這段路況信息對其指導效果會明顯降低甚至失去意義。因此，廣播內容選擇策略和調度策略不僅要能響應最多用戶請求，還要能滿足移動用戶對數據的時效要求。

廣播調度策略是影響無線數據廣播系統性能的關鍵因素。廣播模式中一個完整的數據廣播序列組成一個廣播周期，如何合理地安排一個廣播周期中每個數據出現的頻率以及這些數據之間的順序，使平均訪問時間最少，是數據廣播的主要研究問題之一。對于單項數據廣播的調度方法包括：平坦調度、基于訪問頻率的調度、多盤調度等。在現實情況中我們更多的是同時請求多個數據，例如用戶想同時了解幾個路段的路況信息，相對于單項數據請求，多項數據請求更貼近實際需求。在多數據項廣播中，主要的性能評價標準依然是訪問時間，它指的是從用戶提出請求，到用戶獲得所有訪問數據之間的時間間隔，一個高效的廣播調度策略應當具有較小的平均訪問時間。

部分單項數據調度方法都基于訪問頻率優先的原則，既數據項的訪問頻率越高，廣播的頻率也越高，這種調度策略不能很好的滿足多數據項廣播的場合。在多數據項請求中，頻率和數據項并不是一一對應的關系，按照頻率優先的調度策略或許只能使請求中部分熱門數據及時得到響應，而對于其他非熱門數據則需要等待較長時間，最終使平均訪問時間不能得到有效改善。

目前對多數據項廣播調度策略的研究主要集中在兩個方向，一是面向請求的調度策略，延續了頻率優先的思想，早期的廣播調度策略大多基于這一思想，即應當優先滿足出現頻率較高的請求，基于這一思想的調度策略有QEM算法，改進的QEM算法和GCM算法。另一類是面向數據的調度策略，基本思想是兩個數據項之間存在一定的關系，把數據項之間關系的密切程度作為制定調度策略的參考，這一方面的調度算法有訪問圖算法、QQD算法、平方根算法等。本發明將著重關注數據項之間聯系的密切程度，并在此基礎上充分考慮因為請求頻率的不同導致數據項訪問頻率的變化，依此形成新的調度算法。

在數據廣播模式上可分為三類：周期數據廣播、聯機請求廣播和混合數據廣播。

周期性數據廣播

周期性數據廣播是指服務器利用廣播信道周期地廣播數據，移動用戶不能向服務器提出數據請求，只能被動地接收數據。這種方式將整個帶寬用于廣播數據，沒有上行信道，雖然最大限度地利用了帶寬，但這種廣播模式忽略了移動用戶對數據的動態需求，不能識別用戶和事務的特征以及對數據的時限要求。

聯機請求廣播

聯機請求廣播中給定上行和下行信道，其中上行信道帶寬較低，用于傳送移動用戶的數據請求事務，下行信道用于廣播被用戶頻繁申請的數據信息。在多數據項請求廣播中，移動用戶請求的數據項可能是動態變化的，移動客戶機將數據請求的動態變化通過上行信道通知服務器。這種廣播模式，服務器不知道移動客戶機對廣播數據項的訪問頻率分布，而是根據用戶的動態需求廣播數據。

混合數據廣播

混合數據廣播與聯機請求廣播類似，上行信道用于傳送用戶數據訪問請求。不同點是下行信道被分為周期廣播和聯機請求廣播兩部分，混合數據廣播最大的特點是通過上行信道收集用戶的動態數據請求信息，并以此為依據，不斷地調整周期廣播的內容，盡可能地滿足最多用戶的數據訪問需求，以減少用戶與服務器之間的通信。混合數據廣播比較靈活，既可以減少上行信道的飽和程度，又能最大限度地利用下行廣播的帶寬。