無線網絡中一種新的數據復制算法

摘 要：介紹了靜態數據復制算法，并針對無線網絡提出了基于主節點的動態數據復制算法，該算法可根據主節點所收集的信息的變化重新構架網絡二叉樹，它比靜態算法更能滿足無線網絡節點變化的需要。

關鍵詞：數據復制； 容錯； 主節點； 無線網絡

中圖法分類號：TP302.8文獻標識碼：A

文章編號：1001—3695(2007)02—0094—04

1 引言

隨著通信事業的高速發展，無線網絡已經進入一個新的發展階段。它易安裝、組網靈活，能提供即插即用的網絡連接，無線數據通信已逐漸成為一種重要的通信方式。但無線網絡也有自身的弱點——由于無線網絡技術主要是通過微波信號在空氣中進行數據信號的傳輸，自然天氣情況、建筑物障礙以及與其他微波信號的相互干擾等原因都可以導致無線網絡信號的中斷、衰減，因此對無線網絡中容錯進行的研究就顯得非常重要。數據復制是一種有效的容錯方式，本文提出了一種基于主節點的動態數據復制算法來解決無線網絡中的容錯問題。數據復制是指將相同內容的數據分開存儲在分散式網絡中不同的節點上。復制技術是一種通用、著名的技術，在出現節點失效或網絡故障時，它可以提高數據的可利用性，并且可以通過訪問近處的復制（而不必從遠端的主機）獲取數據，從而提高了效率；同時通過將請求分配給現有的有效復制來平衡服務器的負載。

Fathi Tenzekhti提出了靜態數據復制算法，根據靜態復制策略，復制地點和數目一旦定好后就保持不變，其系統模型為復制的萬維網，包括通過網絡通信相互聯系的許多節點，目標在許多節點被復制。假設網絡拓撲結構由圖G＝（V，E）表示，M＝|V|代表節點的個數，|E|代表鏈接的個數，節點可以是路由、交換機或網絡服務器，鏈接相當于物理鏈接。從客戶端C到服務器端S的請求經各主機所接路由按順序通過這一系列主機，將這一順序稱為路徑n。從所有客戶端到某一個服務器端的路由形成了一棵路由樹，文件請求必須順著這棵樹。客戶端的請求沿著該路由樹到達主服務器，因此對于任何一個網絡服務器I，都可構造出一個根節點為I的生成樹Ti，M個根節點為這M臺網絡服務器的生成樹即可代表整個網絡。靜態模型遵循Read Once Protocol，即網絡服務器端I讀取某目標k僅在所有復制中的某一最佳復制處進行。靜態模型中最佳復制的選擇基于節點j到i的距離以及節點i從節點j讀取k的開銷。靜態模型的目標是在最近的復制點或在能產生最小請求延遲的復制節點上響應讀取請求。在靜態數據復制算法中，節點Pk上保存每個數據k的所有復制的信息列表。此外，每個節點i上都收集如下數據：①距節點i最近的擁有復制k的節點；②路徑n上節點i從節點j讀取數據k的開銷；③路徑n上節點i從節點j讀取數據k的頻率；④節點i到各節點j的距離。

貪婪算法用于解決復制的放置位置問題。其思想如下：對每個數據k，尋找一臺可存放k的復制的服務器i，使得總開銷最小；將k的一份復制放在i上，并繼續在余下的M-1個處理器中尋找下一個復制點；對所有數據重復以上過程，直到找到所有復制點或服務器的容量已滿或無法再容納更多數據為止。

靜態復制算法是基于有線網絡的，在算法中由于復制的位置和數據復制的數目都是在系統設計時就已經固定下來了，所以該算法不能適應無線網絡所具有的可移動性以及網絡狀況受外界干擾大等特點。其模型中每個網絡節點均包含了一些固定的網絡信息，然后根據貪婪算法計算出所有復制的位置。如果使用不變的網絡信息來計算，得出的結果必然無法適應動態的無線網絡結構，并且由于每個網絡節點上都要保存詳細的網絡信息，從而將導致網絡存儲空間的浪費。貪婪算法需要遍歷所有的網絡節點并且在所有節點均無剩余存儲空間時才結束，這種方法的缺點是時間、空間開銷較大；另外在貪婪算法中不能根據數據的重要性決定復制的數目。因此結合這兩種算法并根據動態的無線網絡，本文提出一種新的基于主節點的動態數據復制算法，在該算法中由一中心節點來保存基本的網絡信息，并記錄網絡的變化情況。

2 網絡模型

我們研究的是一種在無線網絡中數據復制的動態分配策略。假設網絡拓撲結構由圖G＝（V，E，S）表示，M＝|V|代表節點的個數，|E|代表鏈接的個數，S代表主節點。主節點是一個網絡集群中的中心節點，記錄整個網絡中的信息，當一個集群與另一個集群傳遞信息時必須通過主節點；節點是網絡服務器，它既是路由器也是數據的存儲空間，它既可以作為網絡的客戶端請求數據，也可以為服務端提供數據；鏈接則相當于物理鏈接，從某客戶端到主節點S的請求經各主機所接路由按一定順序通過這一系列主機，將這一順序稱為路徑n。從所有客戶端到主節點的路由形成一棵路由樹，文件請求必須順著這棵樹。當一個客戶端發出讀文件的請求時，該請求首先根據路徑到達主節點S，然后S根據網絡信息把讀取文件的請求發到某服務端中，再從服務端讀取文件到S后傳回請求客戶端中。例如，當從一個客戶端C1發出讀C2中的文件請求，需要經過的路徑為n1+n2（n1為C1到S的路徑，n2為C2到S的路徑），返回文件請求的路徑也同樣是n1＋n2。在同一個網絡集群中，讀取文件的請求都要首先到達主節點S。

在跨集群的文件讀取中，首先從集群A中的一個客戶端發起讀取文件的請求，該請求先到達本集群的主節點SA中；SA再將請求發送到B集群的主節點SB中；SB根據本集群的網絡信息將該請求發送到存在該文件復制的節點C中。目前為了簡化研究，只考慮單個集群的數據復制問題。

由于無線網絡具有移動性很強的特點，很多節點的位置會經常發生變化，為了便于研究，假定網絡模型中主節點S的位置是固定的（除非發生故障才會變化）。在網絡模型中每隔一定的時間，網絡路徑就會重新分配一次。網絡模型如圖1所示。

3 基于主節點的動態數據復制算法

3.1 網絡信息的放置

網絡信息的放置就是在一個網絡集群中，各種網絡信息如何存放的策略。在無線網絡模型中，訪問任意節點首先到達主節點，所以網絡信息主要存放在主節點中。在主節點中存放了兩張列表，即節點信息表和數據塊信息表。

節點信息表中存放以下信息：每個網絡節點的節點號Cn、每個網絡節點的有效標志、每個網絡節點的坐標（假設主節點的坐標為原點）、每個網絡節點所剩余的存儲空間、每個網絡節點存放的數據塊數目、對應的數據塊號Kn、每個網絡節點到達主節點的路徑N、每個網絡節點到達主節點所花費的開銷Cost以及每個網絡節點被訪問的累計次數等信息。需要說明的是，在一個網絡集群中網絡節點號是唯一的，當某個網絡節點的位置發生變化時，它將主動向主節點發送自己新的節點坐標。例如，一個節點退出網絡集群時首先向主節點發送退出信息，這時主節點會將節點信息表中相應節點的有效標志置為無效；同樣節點的網絡位置變化時首先將其要使用的網絡坐標發送到主節點，主節點則將相應節點信息表中的網絡坐標修改成新的坐標。這種方式只能用于網絡節點主動發生變化時，當網絡節點發生故障或失效而無法正常運行時，主節點就無法了解變化信息。因此為了更準確地了解網絡信息，主節點每隔一定的時間會向本集群中所有網絡節點發出驗證信息，如果沒有收到返回信息則認為此節點已經失效，將其有效標志置為無效；同時主節點每隔一定時間也會向整個網絡集群發出掃描信息查找是否存在新增節點，如果有新增節點則記錄新的節點號以及節點坐標等。

數據塊信息表包含以下信息：每個數據塊號Kn、每個數據塊總的讀取次數、每個數據塊Kn在本網絡集群中總的復制個數Knm、每個復制所在的節點號Cn、每個復制的讀取次數、每個復制的使用標志以及讀取每個數據塊的平均響應時間。另外可以根據每個數據塊的總讀取次數和復制數目來判斷復制個數是否合理，是否需要增加或者減少復制的數目。我們規定在同一時間內，一個復制只能夠被一個客戶端所使用，因此當某一個復制正在被客戶端C1讀取時，如果其他客戶端想要讀取這個復制，就必須等待C1讀取完畢后才能夠進行。

主節點記錄了網絡內的主要信息，而節點則保存了各個數據塊的數據信息。節點除了具有負責存放數據的功能外，還具有通信節點的作用。因此在節點內還應存放必要的網絡信息，包括本網絡節點的節點號、本網絡節點的節點坐標、本網絡節點到主節點的路徑中上層節點的節點號及其坐標等信息。

3.2 節點路徑的生成

在一個無線網絡中，我們可以根據該無線網絡的路徑生成一個以主節點為根的二叉樹。網絡路徑由以下方法得到：首先從主節點開始找尋距離主節點最近的兩個節點，待找到后將其設為主節點的兩個子節點；然后再分別以這兩個節點為父節點在剩余的節點中尋找距離這兩個節點最近的子節點；一直循環下去直到所有的節點都有了父節點，這棵二叉樹就構造成了。除了主節點外，任意一個節點都有唯一的父節點。根據這棵二叉樹，任意一個節點可以通過父節點一直訪問到主節點，這樣就可以得到任意節點的網絡路徑。其基本算法如下：

網絡模型中的開銷Cost，即從一個節點訪問另外一個節點所花的開銷。眾所周知，在無線網絡中兩點距離越遠發送信號所消耗的能量就越大，為了便于研究，我們假設兩點間的開銷等于兩點間距離的平方，即Cost(c1，c2)=L(1，2)×L(1，2)。將生成的路徑和得到的開銷一并記錄到主節點的節點信息表中。

無線網絡的移動性極強。當網絡發生變化時，一些節點位置也隨之發生變化，如新增或減少，原有的網絡路徑不能適應變化后的網絡集群。因此每隔一段時間，主節點要根據新的網絡信息重新構架網絡二叉樹。由于構造算法相同，如果網絡節點沒有發生變化，則重新構造的二叉樹與原來的相同。

3.3 數據塊的放置

在復制算法中，最核心、最重要的是研究數據塊如何放置的問題。數據塊的放置分為兩個部分，即初始化和動態部署。

（1）數據塊的初始化。假設一個初始的無線網絡中有N個網絡節點，M個數據塊。首先取出一個數據塊，尋找距離這個數據塊所在節點最近的一個有剩余存儲空間的節點，然后將此數據塊的一個復制存放在找到的節點中，如果此節點的存儲空間不足則在除此節點以外的所有節點內尋找最近的有足夠存儲空間的節點；繼續取下一個數據塊按上面的方法尋找節點，一直到所有數據塊的復制數目達到初始要求或者沒有剩余存儲空間為止。這樣就完成了數據放置的初始化，然后將初始化的結果存放到主節點的數據塊信息表中。其基本算法如下：

（2）數據塊的動態部署。動態部署的主要依據是數據塊的訪問次數。首先研究數據塊的訪問策略，需要說明的是，在網絡模型中節點既是通信節點也是數據塊存放的服務端，同時還可以是需要訪問數據塊的客戶端。要從一個客戶端訪問一個數據塊首先要從客戶端向主節點請求讀某個數據塊，主節點則根據數據塊信息表查找該數據塊的復制信息，找到距離主節點最近的一個復制。如果該復制正在使用那么繼續查找除該復制外最近的一個復制；如果所有的復制都在使用則返回等待，在等待一段時間后重新從最近的復制開始查找。若找到則先將其使用標志置為正在使用，然后根據節點信息表訪問該節點，讀取數據后再返回給客戶端。當客戶端讀取完該數據塊的復制時，將數據塊信息表中的該復制讀取次數和該數據塊讀取次數加1，并記錄該次讀取數據的響應時間，最后將該復制的使用標志置為未使用。

進行動態數據分配是由于經過一段時間后，可能會發現有些數據塊的復制數目太少而不能夠滿足客戶端的需要；而有些數據塊的復制太多，造成了存儲空間的浪費，因此需要動態地將一些數據塊的復制重新分配。判斷數據塊復制的數目是否合適的主要依據是數據塊的平均響應時間和訪問次數。如果訪問該數據塊的平均響應時間很長并且訪問次數較多，我們即可判定該數據塊的復制數目較少，對此則應該適當地增加該數據塊的復制數目；反之如果該數據塊的平均訪問時間很短并且平均訪問次數遠低于給定的標準值，那么則認為該數據塊的復制數目較多，減少該數據塊的復制數目。

如何增加或減少數據塊的復制數目？①討論數據塊復制數目的增加。當某一數據塊復制較少需要增加其復制數目時，先根據主節點中的數據塊信息和節點信息找到除已有的復制節點外距離原始數據塊最近的有剩余存儲空間的節點，再將該數據塊的復制信息存放在該節點中，并更新數據塊信息表中的信息，將此節點存放到主節點的數據塊信息表中。②研究數據塊復制數目的減少。若需要減少一個數據塊的復制，則應該先根據數據塊信息表中的信息找到該數據塊中所有的復制，查找出訪問次數最少的那個復制，再根據節點信息找到該節點，將節點內的該復制刪除，并將數據塊信息表中相應的復制信息刪除。根據動態數據分配方法可以使存儲空間和客戶端讀取數據響應時間達到一個較好的平衡。其基本算法如下：

4 模擬測試

根據以上算法，我們虛擬了一個網絡模型，在這個網絡模型中分別模擬了靜態算法和主節點動態算法。設定每次測試時間為5min；每8s發起一次讀取請求，每次讀取請求將同時讀取40個數據包；每20s有一個通信節點的坐標隨機發生變化；在主節點動態算法中每40s重組一次網絡。發起請求的客戶端以及讀取的文件都是在所有節點以及數據塊中隨機抽取的。

在這個模擬的無線網絡環境中，首先使用靜態復制算法來確定整個網絡中數據的數目和相應位置；接著進行一段時間的測試，可得到讀取命中率K=L/P(P是在整個測試時間段內總的讀取文件請求次數，L是總的讀取文件成功次數)、平均響應時間Tm＝T/PN(T是成功讀取數據的響應時間的總和，PN為成功讀取數據的次數)；然后使用主節點動態算法來進行試驗。經過相同時間的測試，可得到另一組讀取命中率K以及平均成功響應時間Tm。實驗結果如表1所示。

根據測試結果可以看出，主節點算法的每次讀取成功率都在80%以上，而靜態算法的讀取成功率較低。當節點數和數據包增加時，無論靜態算法還是主節點算法成功率都有所提高。從平均成功響應時間來看，主節點算法比靜態算法所花費的時間少；當節點數和數據包增加時靜態算法所花費的時間明顯增多，而主節點算法沒有較大的變化。

使用主節點算法得到的讀取命中率K遠高于靜態算法，平均響應時間也小于靜態復制算法。這是因為在主節點算法中，每隔一定的時間會將網絡路徑重組一次，因此網絡路徑的可靠性比較高，而且重組后的路徑一般是最佳路徑；而靜態算法中網絡路徑不變，因此在無線網絡中路徑的可靠性較低，節點位置發生變化后路徑沒有變化，所以它不可能是最佳路徑。

因此我們認為主節點列表算法基本可以適應無線網絡數據復

制的需要。當然它也存在缺陷，當讀取請求和網絡節點變化或者讀取請求和網絡路徑重組同時發生時，讀取命中率將大幅度降低，平均響應時間也大幅度增長。解決這些問題將是我們以后研究的目標。 

5 結論

本文提出了一種無線網絡的應用模型，并給出相應的基于主節點的動態數據復制算法。與靜態數據復制相比，該算法的平均響應時間更短，讀取命中率更高，從而能適應無線網絡節點變化的需要。該算法對于研究無線網絡集群中的數據復制有較好的參考價值。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。