分布式數據庫系統動態數據郵遞的QoS模型

尹方超

（河北對外經貿職業學院，河北 秦皇島 066311）

?

分布式數據庫系統動態數據郵遞的QoS模型

尹方超

（河北對外經貿職業學院，河北 秦皇島 066311）

摘 要：在信息通訊中傳統的單播網絡傳輸，一般采用Dijkstra最短路徑算法來建立點到點的最小路徑計算。文章針對廣域網分布式數據庫系統動態、實時數據交換路由問題，對傳統的單播網絡傳輸的Dijkstra算法進行改進，提出了一種平衡網絡負載的QoS的路由算法。

關鍵詞：數據交換；網絡負載；Dijkstra算法

多約束路徑選擇問題是服務質量路由所要研究的重要課題。由于它是一個NPC問題，許多啟發式算法被設計出來。目前，應用QoS比較廣泛的領導主要有多通信技術領域。在這當中的某些帶有啟發性的算法只能應用在網絡通信的路由尋找服務，而在廣域網絡中的分布式數據庫中進行數據傳遞過程中還來沒有過。

在廣域網中，常見的分布式數據庫系統中用來進行數據交換的模式主要是端到端，隨著信息管理水平的提升，原有技術難以解決日益增長的數據交換需求。廣域網絡分布式數據庫節點間進行數據傳遞靠的是定期制定任務的方法來完成。對于各個給定的數據傳遞任務來說，每對源節點和目的節點之間的路徑是固定的，一般將源節點和目的節點的任務規定成一個時間變量。而Dijkstra算法是尋找單路徑當中最短路徑的常用方法。

對于單路徑路數據傳遞來說，最有可能遇到的問題就是用傳統算法所找出的路徑會超出通信鏈路所能夠承擔的負荷，從而給整個網絡造成網絡風暴。本文所用的改進的算法是記錄網絡中所有節點瞬間負載率，對這些負載節點進行對比分析，使其更具合理性，更加優化網絡資源的利用率，從而給整個網絡提供一個相對穩定的負載平衡。

1　傳統QoS路由模型分析

在廣域網絡中，傳的分布式數據節點一般會按一個有向圖的方式來組建，在本文，假設G=｛V，E｝為網絡的有向圖，其中V和E分別表示數據節點集合和鏈路集合，而n和=m則對應分布式網絡中節點和鏈路的數量。假設（u，v）∈E，s為源節點，d為目的節點，從源節點到目的節點的路徑設成P。

那么在這條路由模型的QoS中就可以設置如下：

（1） 數據在網絡信道中的傳輸率模型。

假設：用R（u，v）來表示鏈路（u，v）上的實時數據傳輸率，用Ro來表示傳輸率的閾值，那么在路徑P上任意兩個相鄰節點間的數據傳輸率必須滿足以下要求：

（2）網絡節點負載率。

其中S用來表示節點負載率，當數據傳遞的主節點經過通信鏈路后就能夠獲得其主節點的總數量和空閑子節點的數量，如果子節點空閑的數量越多，那么代表當時的網絡負載越小。所以可以把網絡負載率用子節點的空閑率來表示。

（3）數據傳輸量。

用D來表示在網絡中數據傳輸的總量，這個變量可以按任務配置的多少進行解析和對比，這樣就可以獲得傳輸任務發送的總數據量。

（4）傳輸時間。

用T來表示數據傳輸的時間，那么可以用數據傳輸量和數據傳輸即時速率得到如下公式：

（5）鏈路故障率。

假設用L（u，v 來表示鏈路（u，v）上的實時故障率，L0用來表示故障率的上限，在本模型中必須滿足如下公式：

（6）時間延遲。

假設每個節點和其相鄰節點間的傳輸時間用表示，而正常的通訊時間和表來表示。那么上述參數需滿足如下公式：

在傳統的數據交換鏈路QoS模型中，使其滿足以上幾點，就可以用Dijkstra算法找出從由源節點到目的節點的最短路徑，但是路徑P需滿足以下條件：

其中，當QoS約束在滿足公式（6）的前提下就可以用作路徑尋找，然后在尋找到的諸多可行路徑當中再比較所用時間，哪個時間最少，那么當前的路徑就為最短路徑。

2　高效的Dijkstra尋找最短路徑算法分析

（1）QoS條件服務的預處理過程。

在本次過程當中，需要的數據有3個數據閾值，分別是數據的傳輸率閾值、節點間傳輸時延閾值和節點故障率閾值，而這3個閾值需要滿足以下公式的要求：

其中J（）uk表示和當前節點相鄰的所有點的集合。

（2）給定選擇最短路徑的原理。

（3）用Dijkstra算法求解最短路徑：

3　實驗數據對比分析

在本文當中，擬采用計算機仿真平臺對本實驗數據和網絡環境進行模擬。具體數據設定如圖1所示。

圖1　完整的網絡節點分布圖

在圖1中，數據節點的閾值是當前信道在1M帶寬的前提下的最大傳輸率，因為每次在傳輸數據時總量是不相同的，所以用T（u，v）來表示實時的節點傳輸時間，再用Dijkstra路由算法求出從B點到V點的最短時延。

圖2　Dijkstra算法選路的最短路徑

按照上述要求可以選出從節點B到節點V的路徑為：

計算整個路徑的傳輸時延為16.554。

圖3　平衡網絡負載的Dijkstra路由選路選擇的路徑

同樣可以做出從節點B到節點V的最短路徑：

計算整個路徑的傳輸時延為17.651。

4　結語

從模擬仿真的數據結果可以看出，在改進的算法中，考慮了網絡負載平衡，盡管傳輸的時間可能不是最短，但是從網絡QoS來看，有利于網絡的穩定性，盡可能避免了網絡擁塞。

［參考文獻］

［1］LEBEDEV D.Neural network model for robot path planning in dynamically changing environment［J］.Modeling and Analysis of Information Systems，2001（1）：12-18.

［2］GUANZHENG T，HUAN H，SLOMAN A.Global optimal path planning for mobile robot based on improved Dijkstra algorithm and ant system algorithm.［J］.Journal of Central South University of Technology，2006（1）：80-86.

［3］許輝，吳詩其.LEO衛星網絡中基于螞蟻算法的分布式QoS路由［J］.計算機學報，2007（3）：361-366。

［4］趙有健，張鐵蕾，崔勇.多約束服務質量路由中的路徑壓縮算法［J］.計算機學報，2007（12）：2090-2100。

QoS Model of Dynamic Data Delivery in Distributed Database System

Yin Fangchao
（Hebei Institute of International Business and Economics，Qinhuangdao 066311，China）

Abstract:Information and communication in traditional unicast network transmission of general use Dijkstra shortest path algorithm to establish point-to-point shortest path calculation. In this paper，based on the dynamic and real-time data exchange routing problem of the distributed database system，the traditional unicast network transmission Dijkstra is improved，and a routing algorithm of QoS is proposed to balance the network load.

Key words:data exchange；network load ；dijkstra algorithm

作者簡介：尹方超（1983-），男，河北武安；研究方向：計算機網絡，計算機教學。