有限空間下的自治移動云存儲協議*

崔 波，李 茹，劉 靖，張玉軍，李忠誠

1.內蒙古大學 計算機學院，呼和浩特 010021

2.中國科學院 計算技術研究所 網絡技術研究中心，北京 100190

有限空間下的自治移動云存儲協議*

崔 波1,2，李 茹1+，劉 靖1，張玉軍2，李忠誠2

1.內蒙古大學 計算機學院，呼和浩特 010021

2.中國科學院 計算技術研究所 網絡技術研究中心，北京 100190

自治移動云可以為本地區域內的移動用戶提供臨時的存儲服務。在節點空間有限的情況下，保持數據的持久性是自治移動云存儲服務的一個主要挑戰。提出了一種有限空間下的自治移動云存儲協議，稱為SLAMS（space limited storage protocol for autonomous mobile cloud），其基本思想是通過移動節點之間周期性的信息交互，維護每個數據塊在網絡中的K個副本，將數據塊副本按需存儲在空閑空間較大的節點中。給出了SLAMS協議中的副本維護機制、數據結構和算法、SLAMS協議的詳細設計。仿真實驗結果表明，相對于現有的自治移動云存儲協議Phoenix，SLAMS協議在節點空間有限的情況下，具有較低的數據丟失率，最大可降低50%左右；具有較短的收斂時間，最高可降低95%；具有較少的數據塊存儲開銷，最高可降低約90%；而且SLAMS協議中數據塊維持K個副本的概率明顯提高，最大可提高40%左右。

自治移動云；存儲服務；數據副本維護；數據丟失率

1 引言

自治移動云是一種新的移動云計算[1-3]。自治移動云是由一定區域內臨近的移動設備通過無線連接自組織形成的，它可以向區域內的移動用戶提供臨時的計算和存儲服務。自治移動云具有廣泛的應用前景。在具有網絡基礎設施的條件下，通過移動節點之間的協同，自治移動云可以充分利用移動節點的計算和存儲資源，有效減小蜂窩或WiFi網絡等基礎設施的壓力；在沒有網絡基礎設施，或者由于災難或戰爭導致網絡基礎設施失效的情況下，依靠節點自身的計算和存儲資源，自治移動云可以構建出一個自治的計算平臺或存儲中心。

目前關于自治移動云的研究剛剛起步，現有研究主要集中在系統架構設計[4]、可行性驗證[5-9]及任務分配[10]等方面。Huerta-Canepa等人[4]初步設計了自治移動云的框架，評估了自治移動云的可行性；Li等人[5]通過跟蹤和理論分析，說明了自治移動云向移動節點提供移動應用服務的可行性；Fahim等人[6]比較了移動節點使用傳統移動云、Cloudlets和自治移動云完成任務需要的時間以及能量消耗，得出了將任務遷移到自治移動云上最高可以降低50%的時間以及減少26%的能量消耗的結論，說明了自治移動云的有效性。

自治移動云的主要應用包括計算和存儲兩個方面[11-14]。在計算服務方面，Miluzzo等人[11]簡單討論了自治移動云計算的管理方法以及獎勵機制；Shi等人[12]設計并實現了Serendipity系統，該系統可以使移動節點使用其他節點的計算資源，主要研究如何對計算任務建模，以及如何將計算任務分配到移動設備上。提供數據存儲服務是自治移動云的另一個重要應用，Marinelli[13]使用Hyrax平臺實現了移動設備間文件共享的存儲服務；Arif等人[14]利用飛機場停車場中的車輛建立自治的數據中心，可以為用戶提供存儲服務。

數據的持久性是自治移動云存儲服務面臨的主要挑戰，主要原因在于：（1）移動設備可能會隨機地離開或者加入到網絡中；（2）移動設備可能關機或者失效；（3）移動設備可能由于空間有限而刪除一些舊的數據來存儲新的數據；（4）移動設備間的無線通信不穩定，容易出錯。Marinelli[13]將Hadoop移植到移動設備上，實現了Hyrax平臺，利用該平臺，移動用戶可以實現有效的數據共享，保持數據的持久性。但是該服務的實現需要在移動設備上使用Hyrax平臺，平臺的設計是建立在特定系統上的，適應性較差。Panta等人[15]提出了一種為網絡中的每個數據塊維護K個副本的方法來保持自治移動云中數據的持久性。首先通過數學分析驗證了方法的可行性，然后提出了一種分布式協議，稱為Phoenix，該協議使用一種分布式的算法來確保一定程度的存儲冗余。該協議的突出問題是，沒有考慮節點存儲空間的有限性。通過實驗發現，在網絡節點存儲空間有限的情況下，該協議維持K個副本的概率會大大降低，維持數據塊K個副本的收斂時間會增加，更為嚴重的是會引起數據的顯著丟失。需要指出的是，本文提到的有限空間是指移動節點的存儲容量是有限的，不能存放任意多的數據。

針對以上問題，本文提出了一種有限空間下的自治移動云存儲協議（space-limited storage protocol for autonomous mobile cloud，SLAMS）。該協議的目的也是為網絡中的每個數據塊維護K個副本，保持數據的持久性。簡單來說，在考慮節點空間有限的情況下，SLAMS協議將數據副本按需存放在空閑空間比較大的節點中，當網絡中某個數據塊的副本數量不足K（設為j）時，SLAMS協議將從沒有該數據塊的節點中選擇空閑空間最大的K-j個節點存儲該數據塊。這樣一方面可以盡量避免由于空間已滿的節點接收新數據而刪除舊數據導致的數據丟失問題；另一方面可以降低副本的收斂時間，而且還能夠使數據塊維持K個副本的概率較高。和Phoenix相比，SLAMS協議在空間有限的情況下，具有較低的數據丟失率、較短的收斂時間和較少的數據塊存儲開銷，而且SLAMS協議中數據塊維持K個副本的概率也比較高。

本文組織結構如下：第2章描述了研究背景，分析了Phoenix協議，給出了協議的評價指標；第3章給出了SLAMS協議，描述了其中的副本維護機制、數據結構和算法以及SLAMS協議的詳細設計；第4章通過實驗比較分析了SLAMS協議和Phoenix協議的數據塊丟失率、維持K個副本的概率、平均收斂時間和數據塊存儲開銷；第5章總結全文。

2 研究背景

2.1 協議分析

Phoenix[15]是自治移動云提供存儲服務的可靠協議，也是本文的主要對比協議。該協議通過為網絡中的每個數據塊維護K個副本的冗余方法來保持自治移動云中數據的持久性。考慮到缺少全局的網絡狀態信息以及網絡的動態性等問題，Phoenix協議使用一種分布式的算法為每個數據塊存儲K個副本。Phoenix協議的主要思路是通過節點間周期性的信息交互，為每個數據塊維護一定數量的副本，基本原理如下：

（1）每輪周期開始時，節點啟動一個隨機定時器，如果某個節點在定時器到期時沒有收到其他節點的公告消息，那么該節點成為發起節點，然后選擇并廣播某個數據塊bi的公告消息。

（2）如果其他節點包含該數據塊bi，并且該節點收到了至少K個bi的公告消息，它將刪除自己存儲的數據塊bi；否則，它將廣播bi的公告消息。

（3）如果其他節點不包含該數據塊bi，但是它收到了K個bi的公告消息，它不做任何操作；否則，它將驗證網絡中是否確實只有小于K個bi的副本的存在。當驗證結束后，如果網絡中有至少K個bi的副本，該節點不做任何操作；否則，它將向發起節點發送請求消息，請求下載數據塊bi。

（4）發起節點在收到請求下載消息后，將廣播數據塊bi，不僅請求者會存儲數據塊bi，其他所有沒有數據塊bi的節點也要存儲數據塊bi，產生的多余副本將在下一輪bi的調整周期中刪除。

從上面的分析可以看出：Phoenix協議發起節點廣播數據塊時，不僅請求者會存儲該數據塊，其他將要發送請求的節點也要存儲該數據塊，導致系統中存在多余數據塊副本，增大副本的收斂時間；在節點空間有限的情況下，多余副本的存在會浪費寶貴的存儲空間，增加數據塊丟失率，降低系統中維持K個副本的概率；同時多余副本的存儲和刪除會增加數據塊的存儲開銷，增加移動設備的能量消耗。

本文提出了一種新的自治移動云存儲協議，并通過數據塊的丟失率、維持K個副本的概率、平均收斂時間和數據塊存儲開銷4個指標來評價協議的性能。

2.2 評價指標

設網絡中的節點數量為N，不同數據塊的數量為B，系統中需要為每個數據塊維護的副本數量為K，一個節點為每個數據塊最多只存放一個副本，系統的運行時間段為T。設bi(i=1,2,…,B)為網絡中的一個數據塊，copy(i,t)表示標號為i的數據塊bi在t時刻的副本數量(t=1,2,…,T)，check(i,t,j)用來判斷某個數據塊的副本數量是否為特定值j，即copy(i,t)是否為j個（j=0,1,…,N）。

定義1（數據塊的丟失率block_lost_rate）在時間段T內，副本數為0的數據塊的個數占所有數據塊總數的百分比，即：

協議的主要目的是為了保持數據的持久性，防止數據丟失。因此，數據塊的丟失率是評價移動云存儲協議的一個核心指標，數據塊的丟失率越低則說明協議的可靠性越好。

定義2（維持K個副本的概率probability(K)）在時間段T內，副本數為K的數據塊的個數占所有數據塊總數的百分比，即：

當副本數小于K的比例較高時，由于節點的移動，數據丟失的可能性較大；當副本數大于K的比例較高時，節點需要為多余的副本分配空間，增加節點的存儲負擔。

數據塊副本的維護是指副本數量小于K的數據塊從被選擇調整開始到副本數首次調整為K的過程；單個數據塊副本的一次維護的收斂時間是指副本數量小于K的數據塊bi從被某一節點nj選擇調整開始，到副本數首次調整為K的時間。

設c(i,j)表示時間段T內nj發起的數據塊bi的副本維護的次數；time(bi,nj,k)表示時間段T內nj發起的第k次數據塊bi的副本維護的時間；time(nj)表示時間段T內節點nj發起的所有數據塊副本維護的總時間；c(nj)表示時間段T內節點nj發起的所有數據塊副本維護的總次數，其中j=1,2,…,N，即：

定義3（平均收斂時間convergence_time）在時間段T內，系統中所有數據塊副本維護的平均時間，即：

收斂時間體現了數據塊副本數維持小于K以及維持大于K的時間，數據塊副本數維持小于K的時間越長，節點的移動數據塊丟失的可能性越大；數據塊副本數維持大于K的時間越長，空間浪費越嚴重，節點空間有限時數據塊丟失的可能性越大。

設ins_del_bnum(nj)表示時間段T內節點nj存儲和刪除數據塊的次數(j=1,2,…,N)。

定義4（數據塊存儲開銷ins_del_block_number）在時間段T內，系統中所有節點存儲和刪除數據塊的總次數，即：

數據塊的存儲開銷體現了節點存儲和刪除數據塊的次數，節點存儲和刪除數據塊的次數越多，節點的能量消耗越大。

3 面向有限空間的優化存儲協議

本章給出一種有限空間下的自治移動云存儲協議，其基本思想是通過移動節點之間周期性的信息交互，維護每個數據塊在網絡中的K個副本，并將數據塊副本按需存儲在空閑空間較大的節點中。

3.1 副本維護機制

為了保持系統中每個數據塊有K個副本，節點需要周期性地維護數據塊的副本數，一個周期只維護一個數據塊，一個周期即為一個調整輪次。數據塊副本的維護需要節點協作完成，本文將維護某個數據塊bi副本的節點分為3種角色：數據塊bi副本維護的發起節點（initiator node，IN）、擁有數據塊bi的節點（follower node withbi，FN_Y）和沒有數據塊bi的節點（follower node withoutbi，FN_N）。

某一時刻下網絡中數據塊的副本數量不同，存在以下兩種具體的副本維護機制（圖1）。

（1）數據塊的副本數量大于K（如圖1（a））

①發起節點IN廣播數據塊bi的公告消息。

②擁有數據塊bi的節點FN_Y如果收到小于K個bi的公告消息，則廣播數據塊bi的公告消息；否則，刪除節點中存儲的數據塊bi。

（2）數據塊的副本數量小于K（如圖1（b））

①發起節點IN廣播數據塊bi的公告消息。

②沒有數據塊bi的節點FY_N向發起節點發送本節點的空閑空間消息。

發起節點IN收到空間消息后，將節點空間信息存儲在本地。如果發起節點IN收到了j(j〈K-1)個數據塊bi的公告消息，它將選擇空閑空間最大的K-1-j個節點，并向這些節點發送數據塊bi。

Fig.1 Block copy maintenance mechanism圖1 數據塊副本的維護機制

3.2 數據結構與算法

為實現SLAMS協議中的副本維護機制，節點需要維護兩個數據結構：數據塊列表（block list，BL）和節點空閑空間列表（freespacelist，FSL）（圖2）。其中數據塊列表BL用于維護節點存儲的數據塊的信息，包括數據塊ID（BLOCK_ID）和數據塊的狀態（BLOCK_ STATUS）；空閑空間列表FSL用于臨時存儲沒有數據塊bi的節點FY_N的空閑空間信息：包括節點ID（NODE_ID）和空閑空間（NODE_SPACE）。BLOCK_ ID是數據塊的唯一標識；BLOCK_STATUS有兩種狀態：0表示不穩定，1表示穩定；NODE_SPACE為節點的空閑空間，表示該節點可存儲的數據塊的數量。當一個節點知道網絡中某個數據塊有K個副本時，它就認為該數據塊的狀態是穩定的，否則該數據塊是不穩定的。

Fig.2 Data structure of SLAMS protocol圖2 SLAMS協議數據結構

算法1發起節點的數據塊維護算法

如果發起節點IN的數據塊列表BL中有不穩定的數據塊，Block_Choose()將隨機選擇一個不穩定數據塊bi并向其他節點廣播數據塊bi的公告消息；否則，Block_Choose()將在BL中隨機選擇廣播一個數據塊bi的公告消息。發起節點IN還需要負責接收其他節點的空間信息，并維護臨時的空閑空間列表FSL，決定是否需要向其他節點以及向哪些節點發送該數據塊bi（算法1）。其他節點在收到數據塊bi的公告消息后，首先要在BL中查找是否有數據塊bi的信息，如果有，節點根據收到的數據塊bi的公告消息數來決定是保留或刪除數據塊bi；如果沒有，節點根據收到的數據塊bi的公告消息數來決定是否向發起節點發送空間信息，請求存儲數據塊bi（算法2）。

算法2接收節點的數據塊維護算法

3.3 協議的詳細設計

SLAMS協議中主要涉及3種角色的節點：發起節點、擁有數據塊bi的節點和沒有數據塊bi的節點。節點的角色是根據發起者的確定而不斷變化的，數據塊的維護由這3種節點協作完成。因此，協議中主要包括：發起者的確定、擁有數據塊bi的節點的行為、沒有數據塊bi的節點的行為、發起者的行為。

發起者的確定。參考文獻[15]，發起者的確定方法如下：在每個調整輪次開始時，每個節點維護一個公告定時器，時間是從0到ta的隨機值（如果節點擁有不穩定的數據塊，ta選擇最小公告等待時間tamin，否則，ta選擇最大公告等待時間tamax）。如果當某個節點的公告定時器到期時，沒有收到任何數據塊的公告消息，它就成為發起者，選擇廣播某個數據塊bi的公告消息（如圖3（a）中的節點n3在t1時刻的行為）。

擁有數據塊bi的節點行為。基本思想是擁有數據塊bi的節點根據當前網絡中數據塊bi的副本數決定是保留還是刪除本節點中的數據塊bi。主要過程是擁有數據塊bi的節點收到公告消息后將啟動一個回復定時器，時間是從0到tr的隨機值。當定時器到期時，如果節點收到了小于K個數據塊bi的公告消息，它將廣播數據塊bi的公告消息（如圖3（a）中的節點n4在t2時刻的行為）；同時如果節點收到了K-1個公告消息，它將把數據塊bi的狀態設置為1，然后啟動下一輪的公告定時器。如果節點收到了K個公告消息，它將刪除本節點存儲的數據塊bi（如圖3（a）中的節點n2在t2′時刻的行為），啟動下一輪的公告定時器。具體方法如算法2中的第1行到第7行所示。

Fig.3 Adjustment for copies of block圖3 數據塊副本數的調整

沒有數據塊bi的節點行為。基本思想是沒有數據塊bi的節點根據當前網絡中數據塊bi的副本數決定是否向發起節點發送空間消息，請求存儲副本。主要過程是沒有數據塊bi的節點收到公告消息后啟動一個請求定時器，時間為固定值tr+tw。如果在定時器到期時，該節點收到了至少K個數據塊bi的公告消息，它將啟動下一輪的公告定時器；否則，它將向發起節點發送本節點空閑空間的消息（如圖3（b）中的節點n1和n3在t2時刻的行為），啟動下一輪的公告定時器。具體方法如算法2中的第9行到第12行所示。

發起節點的行為。基本思想是發起節點根據當前網絡中數據塊bi的副本數來決定是否需要以及向哪些沒有數據塊bi的節點發送數據塊bi。主要過程是當發起節點廣播公告消息后，它將啟動一個回復等待定時器，時間為固定值tr。當定時器到期時，如果該節點收到了至少K-1個數據塊bi的公告消息，它將數據塊bi的狀態設置為1，然后啟動下一輪的公告定時器；否則，它將啟動一個等待空間消息定時器，時間為固定值2tw。當定時器到期時，如果發起節點沒有收到任何空閑空間信息，它將進入驗證階段；否則，如果發起節點收到了當前輪次的節點發來的空閑空間信息（包括節點NODE_ID和空閑空間NODE_SPACE），它將按照空間的大小按序將信息存儲到本地空閑空間列表FSL中。如果發起節點沒有收到至少K-1個數據塊bi的公告消息，它將驗證網絡中是否確實只有小于K個數據塊bi存在（如圖3（b）中的節點n4在t3時刻的行為）。如果在驗證完成后，發起節點發現網絡中確實只有小于K個數據塊bi存在，它將進入數據塊bi的發送階段（如圖3（b）中的節點n4在t4時刻的行為）；否則，它將啟動下一輪的公告定時器。具體方法如算法1所示。

驗證階段。驗證可以避免不必要的數據塊發送，因此驗證階段是有必要的。避免不必要的數據塊發送可以減少帶寬的使用和節約能源，因此在發送數據塊bi之前，發起節點先向網絡中廣播一個驗證消息，詢問其他節點是否含有數據塊bi（如圖3（b）中的節點n4在t3時刻的行為）。當節點收到該驗證消息后，如果含有數據塊bi，它們將向發起節點發送確認消息。當發起節點收到至少K-1個確認消息，或者驗證次數達到一定的閾值（Nver）時，它將停止發送驗證消息。如果在驗證階段發起節點收到了至少K-1個確認消息，它將啟動下一輪的公告定時器；否則，如果當驗證結束后，它還沒有收到至少K-1個確認消息，將按需地向沒有數據塊bi的節點發送數據塊bi。

數據塊bi的發送與接收。在驗證結束后，如果發起節點只收到了j(j〈K-1)個確認消息，它將在空閑空間列表FSL中選擇空間最大的K-1-j個節點作為數據塊bi的接收節點，然后廣播數據塊bi（如圖3（b）中的節點n4在t4時刻的行為）。當其他節點收到廣播數據塊bi后，首先檢查自己是不是接收節點，如果是，則保存該數據塊bi（圖3（b）中的節點n3在t4時刻的行為）；否則，將丟棄該數據塊bi。

4 仿真實驗

4.1 實驗環境和參數

仿真實驗基于TinyOS[16]的TOSSIM[17]仿真平臺，實現了本文提出的SLAMS協議，并與Phoenix協議進行對比分析。仿真場景設置為：考慮3種不同的網絡狀態，即稀疏、正常和稠密，根據不同的網絡狀態分別選擇由5、25和50個節點組成的一跳網絡。這些節點隨機地分布在一個15 m×15 m的地理區域內，為了忽略信號不穩定對協議的影響，將節點間的信號增量設置得足夠大（大于-70 dBm）。實驗初始時可假設數據塊平均分布在各個節點中。

仿真實驗涉及的具體參數說明及賦值見表1。實驗具體設計思路為：在N個節點組成的網絡中，每個節點的容量（可存儲的數據塊的數量）為C，若為每個數據塊（不同數據塊的數量為B）維護K個副本，則需要的總容量為Cn，假設網絡中節點的總容量為Ct，則Cn=B×K，Ct=N×C。仿真實驗將通過調整參數N、B、C、K和P的值，觀察2.2節所提出性能評價指標的變化，以此驗證SLAMS協議的優勢。具體而言，為有效分析SLAMS協議在節點空間有限的情況下的性能優勢，實驗將以Ct和Cn的比值作為自變量參數，重點考慮該比值在小于1（即系統提供的容量小于副本維護需要的容量）、等于1（即系統提供的容量等于副本維護需要的容量）、大于1（即系統提供的容量多于副本維護需要的容量）等多種場景下，參數N、B、C、K和P的調節對數據塊的丟失率、維持K個副本的概率、平均收斂時間以及數據塊存儲開銷等4個性能指標的影響。此外，每個節點在MOVE_MIN和MOVE_MAX之間會選擇一個隨機的時間間隔，在網絡中的節點將在該間隔時刻以概率P離開網絡；而之前離開網絡的節點將在該間隔時刻以概率Q進入網絡。

Table 1 Descriptions and valid values of parameters表1 實驗參數的說明與設置

需要指出的是，在仿真實驗中，選擇Q=0.5和P= 0.05，0.10，0.20取值組合，分別表示移動節點以較慢速度、正常速度和較快速度離開網絡；B值取50、250和500分別表示網絡中數據的狀態為較少、正常和較多。一個較優的K的取值主要與節點離開和加入網絡的概率、數據的重要性以及網絡鏈路的狀態等因素有關，本文主要考慮節點的離開和加入網絡的概率。當K等于2時，擁有相同數據塊副本的節點同時離開網絡的概率比較低，數據可以保持較高的持久性；當K大于2時，數據可以保持更高的持久性，但是會消耗更多的存儲空間。因此，鑒于本文重點關注移動節點存儲容量有限情況下副本的分配策略，選擇K=2為典型代表值，這樣可以保持一個較高的數據持久性。同時，簡要分析N、B、C、P值確定的情況下，K值與數據丟失率的關系。

不失一般性，每2 s記錄一次網絡中的節點狀態（節點中存儲的數據塊），每個實驗的仿真時間為2 000 s。為了使實驗結果更為客觀，并消除隨機性因素，本文將每項實驗進行20次后計算平均值，從而得到最終的實驗結果。

4.2 實驗結果與分析

本節將分別對數據塊的丟失率、維持K個副本的概率、平均收斂時間以及數據塊存儲開銷4個性能指標的仿真實驗結果進行分析，以此說明SLAMS協議較Phoenix協議的優勢所在。

4.2.1 數據塊的丟失率

Fig.4 Block lost rate with differentCt/Cnvalues圖4 數據塊的丟失率隨Ct與Cn比值的變化關系

圖4 顯示了不同網絡狀態下SLAMS協議和Phoenix協議數據塊丟失率的比較，橫坐標表示Ct與Cn的比值，縱坐標表示數據塊的丟失率，Ct表示網絡中節點的總容量，Cn表示為每個數據塊維護K個副本需要的總容量。其中，圖4（a）顯示的是N=5個節點的網絡中B=50個數據塊維護K=2個副本時，兩種協議數據塊的丟失率隨Ct與Cn比值的變化關系；圖4（b）顯示的是在圖4（a）的基礎上變化節點數N的值（N=5到N=25）時，兩種協議數據塊的丟失率隨Ct與Cn比值的變化關系；圖4（c）顯示的是在圖4（b）的基礎上變化數據塊數B的值（B=50到B=250）時，兩種協議數據塊的丟失率隨Cn與Ct比值的變化關系；圖4（d）顯示的是N=50，B=500時，兩種協議數據塊的丟失率隨Ct與Cn比值的變化關系。從圖4可以看出：（1）在相同的移動概率下，Ct與Cn的比值小于一定程度時，如在圖4（b）中，Ct/Cn小于2.5時，SLAMS協議比Phoenix協議有較低的數據塊丟失率，最大相差50%左右。這是因為在副本維護過程中，Phoenix協議會產生多余的數據塊的副本，節點空間有限時為了存儲多余的副本會刪除舊的數據塊，增加數據塊的丟失率，而SLAMS協議基本不會產生多余副本。（2）隨著節點數量的增加，如從圖4（a）到圖4（b）（節點數N=5到N=25），SLAMS協議在數據塊丟失率方面的優勢越來越明顯，當Ct/Cn=1.0時數據塊的丟失率最大可降低50%左右。這是因為節點空間有限時，節點數越多，Phoenix協議中同一數據塊的副本數越多，多余的副本占用的空間越多，數據塊的丟失率越大。（3）隨著節點數量的增加，Phoenix協議數據塊丟失率達到穩定值時Ct/Cn值越大，如從圖4（a）到圖4（c），Ct/Cn的值從1.5增加到2.25，而SLAMS協議數據塊丟失率達到穩定值時Ct/Cn值基本不變。這是因為節點數越多，Phoenix協議產生的多余副本數越多，存儲多余副本所需要的空間也越大，而SLAMS協議基本不會產生多余的副本。

為了驗證兩種協議數據塊的丟失率和K的關系，選擇圖4（c）中Ct/Cn=1.0時的網絡狀態。這是因為此時節點數量和數據塊數量足夠大，并且兩種協議數據塊丟失率方面的差距比較明顯。同時，兩種協議的差距受節點移動性的影響不大，因此選擇一種離開率P=0.05時移動狀態作為代表。當節點數一定時，維護的副本數K越大，需要存儲副本的節點越多，Phoenix協議多余的副本數量相對越小，Phoenix協議的丟失率和SLAMS越接近，如圖5所示。

總的來說，在節點空間有限的情況下，SLAMS協議數據塊的丟失率低于Phoenix協議，K值越小、N值越大，SLAMS協議在數據塊丟失率方面的優勢越明顯。數據塊丟失率達到穩定時，SLAMS協議需要的節點空間總容量低于Phoenix協議，N值越大，SLAMS協議的優勢越明顯。

Fig.5 Block lost rate with differentKvalues圖5 數據塊的丟失率隨K值的變化關系

4.2.2 維持K個副本的概率

圖6顯示了不同網絡狀態下（同圖4）SLAMS協議和Phoenix協議維持K個副本的概率比較，橫坐標表示Ct與Cn的比值，縱坐標表示數據塊副本數為K的概率。從圖6可以看出：（1）在相同的節點移動概率下，Ct與Cn的比值小于一定程度時，如在圖6（c）中，Ct/Cn小于2.5時，SLAMS協議維護K個副本的概率高于Phoenix協議。這是因為在節點空間有限時，和Phoenix協議相比，SLAMS協議具有較低的數據塊丟失率，即SLAMS協議副本為0的概率較低，并且SLAMS協議具有較低的副本大于K的概率。（2）隨著節點數的增加，如從圖6（a）到圖6（b）（節點數N=5到N=25），當Ct/Cn小于2.5時，SLAMS協議維持K個副本的概率明顯高于Phoenix協議，最大相差40%左右（Ct/Cn=1.0時）。這是因為節點空間有限時，Phoenix協議數據塊的丟失率會隨著節點數的增加而顯著增加，導致副本數為0的概率顯著增加，維持K個副本的概率顯著減少。（3）隨著數據塊數量的增加，如從圖6（b）到圖6（c）（數據塊數B=50到B=250），當Ct與Cn的比值達到一定程度時，如Ct/Cn大于等于2時，SLAMS協議維持K個副本的概率的優勢也在增加。這是因為，此時兩種協議數據塊的丟失率基本穩定，需要維護的數據塊較多，維護的數據塊越多，Phoenix協議中副本數大于K的概率越高，副本數等于K的概率越低，而SLAMS協議受數據塊數目影響較小，因此SLAMS協議優勢越明顯。

4.2.3 平均收斂時間

圖7顯示了不同網絡狀態（同圖4）下SLAMS協議和Phoenix協議為數據塊維護K=2個副本時平均收斂時間的比較，橫坐標表示Ct與Cn的比值，縱坐標表示副本的平均收斂時間。從圖7可以看出：（1）在相同的移動概率下，當Ct與Cn的比值小于等于2.5時，SLAMS協議副本的收斂時間明顯小于Phoenix協議，如在圖7（a）中，Ct/Cn=1.0時，Phoenix協議的副本收斂時間約為SLAMS協議的20倍。這是因為當數據塊的副本數量小于K時，SLAMS協議是按需地調整副本的數量，可以通過一個調整周期將副本數小于K調整到等于K，而Phoenix在維護數據塊副本的過程中，會產生多余副本，多余副本的刪除還需要額外的調整周期，即副本數量的維護需要經歷從小于K，到大于K，再到等于K的過程。由于調整過程不具有連續性，即該數據塊的副本通過一輪調整從小于K到大于K后，該數據塊還需要等待一定的時間才能再次被選擇，進而刪除多余的副本，增加了副本收斂時間。（2）隨著數據塊個數的增加，如從圖7（b）到圖7（c）（數據塊數B=50到B=250），當Ct與Cn的比值達到一定程度時，如Ct/Cn等于2.5時，Phoenix協議副本的收斂時間顯著增加，增加了約4倍，SLAMS協議副本收斂時間基本不變。這是因為Phoenix協議副本的維護需要兩個階段（副本數從小于K到大于K，從大于K到等于K），這兩個階段不是連續的，需要一定的數據塊選擇的等待時間。由于每輪調整數據塊的選擇是隨機的，數據塊越多，數據塊被選擇等待的時間越長，收斂時間越長，而SLAMS協議副本的維護往往是只要一個調整周期，收斂時間與數據塊的數量基本沒有關系。

Fig.6 Probability of keepingKcopies圖6 維持K個副本的概率

4.2.4 數據塊的存儲開銷

圖8顯示了不同網絡狀態（同圖7）下SLAMS協議和Phoenix協議為數據塊維護K=2個副本時數據塊存儲開銷的比較，橫坐標表示Ct與Cn的比值，縱坐標表示數據塊的存儲開銷（節點存儲和刪除數據塊的總次數）。從圖8可以看出：（1）在相同的移動概率下，當Ct與Cn的比值小于等于2.5時，SLAMS協議數據塊的存儲開銷少于Phoenix協議，如在圖8（a）中，Ct/Cn=1.5時，Phoenix協議數據塊的存儲開銷約為SLAMS協議的3倍。這是因為和SLAMS協議相比，Phoenix協議在數據塊副本數的維護過程中會產生多余的副本，增加了節點存儲和刪除數據塊的操作次數。（2）隨著節點數量的增加，如從圖8（a）到圖8（b）（節點數N=5到N=25），SLAMS協議在數據塊存儲開銷方面的優勢越來越明顯，如在Ct/Cn=2.0時，Phoenix協議數據塊的存儲開銷約為SLAMS協議的10倍(P=0.05)。這是因為節點數越多，Phoenix協議中同一數據塊的副本數越多，為數據塊維護K個副本需要的數據塊存儲和刪除的操作越多。

Fig.7 Average convergence time圖7 平均收斂時間

5 總結

在節點空間有限的情況下，保持數據的持久性是自治移動云存儲的一個主要挑戰。本文提出了一種有限空間下的自治移動云存儲協議（SLAMS），可以有效地利用有限的移動節點的存儲資源，實現為自治移動云中的移動節點提供可靠存儲服務；通過將數據塊的副本存儲在空閑空間比較大的節點中，能夠盡量避免由于空間有限導致的數據塊丟失的問題。本文通過多組實驗驗證了SLAMS協議的性能。實驗結果表明，和現有的自治移動云存儲協議Phoenix相比，在節點空間有限的情況下，SLAMS協議能夠有效降低數據塊的丟失率，節點數越多，K值越小，SLAMS協議的優勢越明顯；SLAMS協議數據塊維持K個副本的概率較高，節點數越多，數據塊數越多，SLAMS協議優勢越明顯；具有較短的副本收斂時間，數據塊越多，SLAMS協議優勢越明顯；具有較少的數據塊存儲開銷，節點數越多，SLAMS協議優勢越明顯。

Fig.8 Overhead of block storage圖8 數據塊的存儲開銷

[1]Fernando N,Loke S W,Rahayu W.Mobile cloud computing: a survey[J].Future Generation Computer Systems,2013,29 (1):84-106.

[2]Fernando N,Loke S W,Rahayu W.Dynamic mobile cloud computing:ad hoc and opportunistic job sharing[C]//Proceedings of the 2011 4th IEEE International Conference on Utility and Cloud Computing,Victoria,Australia,Dec 5-8, 2011.Piscataway,USA:IEEE,2011:281-286.

[3]Shi C,Ammar M H,Zegura E W,et al.Computing in cirrus clouds:the challenge of intermittent connectivity[C]//Proceedings of the 1st ACM Edition of the MCC Workshop on Mobile Cloud Computing,Helsinki,Finland,Aug 17,2012. New York:ACM,2012:23-28.

[4]Huerta-Canepa G,Lee D.A virtual cloud computing provider for mobile devices[C]//Proceedings of the 1st ACM Workshop on Mobile Cloud Computing&Services:Social Networks and Beyond,San Francisco,USA,Jun 15,2010. New York:ACM,2010:6.

[5]Li Yujin,Wang Wenye.Can mobile cloudlets support mobile applications?[C]//Proceedings of the 33rd Annual IEEE International Conference on Computer Communications, Toronto,Canada,Apr 27-May 2,2014.Piscataway,USA: IEEE,2014:1060-1068.

[6]Fahim A,Mtibaa A,Harras K A.Making the case for computational offloading in mobile device clouds[C]//Proceedings of the 19th Annual International Conference on Mobile Computing&Networking,Miami,USA,Sep 30-Oct 4,2013.New York:ACM,2013:203-205.

[7]Li Yujin,Sun Lei,Wang Wenye.Exploring device-to-devicecommunication for mobile cloud computing[C]//Proceedings of the 2014 IEEE International Conference on Communications,Sydney,Australia,Jun 10-14,2014.Piscataway, USA:IEEE,2014:2239-2244.

[8]Chen C A,Won M,Stoleru R,et al.Energy-efficient faulttolerant data storage and processing in mobile cloud[J]. IEEE Transactions on Cloud Computing,2015,3(1):28-41.

[9]Mtibaa A,Fahim A,Harras K A,et al.Towards resource sharing in mobile device clouds:power balancing across mobile devices[J].ACM SIGCOMM Computer Communication Review,2013,43(4):51-56.

[10]Lu Zongqing,Zhao Jing,Wu Yibo,et al.Task allocation for mobile cloud computing in heterogeneous wireless networks[C]//Proceedings of the 2015 24th International Conference on Computer Communication and Networks,Las Vegas,USA,Aug 3-6,2015.Piscataway,USA:IEEE,2015:1-9. [11]Miluzzo E,Cáceres R,Chen Y F.Vision:mClouds-computing on clouds of mobile devices[C]//Proceedings of the 3rd ACM Workshop on Mobile Cloud Computing and Services, Low Wood Bay,Lake District,UK,June 25,2012.New York,USA:ACM,2012:9-14.

[12]Shi C,Lakafosis V,Ammar M H,et al.Serendipity:enabling remote computing among intermittently connected mobile devices[C]//Proceedings of the 13th ACM International Symposium on Mobile Ad Hoc Networking and Computing,Hilton Head Island,USA,June 11-14,2012. New York,USA:ACM,2012:145-154.

[13]Marinelli E E.Hyrax:cloud computing on mobile devices using MapReduce[D].Pittsburgh,USA:Carnegie Mellon University,2009.

[14]Arif S,Olariu S,Wang J,et al.Datacenter at the airport:reasoning about time-dependent parking lot occupancy[J].IEEE Transactions on Parallel and Distributed Systems,2012,23 (11):2067-2080.

[15]Panta R K,Jana R,Cheng F T,et al.Phoenix:storage using an autonomous mobile infrastructure[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(9):1863-1873.

[16]Levis P,Madden S,Polastre J,et al.Tinyos:an operating system for sensor networks[M]//Ambient Intelligence.Berlin:Springer,2005:115-148.

[17]Levis P,Lee N,Welsh M,et al.TOSSIM:accurate and scalable simulation of entire TinyOS applications[C]//Proceedings of the 1st ACM International Conference on Embedded Networked Sensor Systems,Los Angeles,USA,Nov 5-7, 2003.New York:ACM,2003:126-137.

CUI Bo was born in 1983.He received the M.S.degree in software engineering from Wuhan University in 2008. Now he is a Ph.D.candidate and lecturer at Inner Mongolia University,and the member of CCF.His research interests include VANET and mobile distributed storage,etc.

崔波（1983—），男，山東濟寧人，2008年于武漢大學獲得碩士學位，現為內蒙古大學計算機學院博士研究生、講師，CCF會員，主要研究領域為車聯網，移動分布式存儲等。

LI Ru was born in 1974.She received the Ph.D.degree in computer science from Institute of Computing Technology, Chinese Academy of Sciences in 2005.Now she is a professor and Ph.D.supervisor at Inner Mongolia University, and the senior member of CCF.Her research interests include wireless network and future Internet,etc.

李茹（1974—），女，內蒙古呼和浩特人，2005年于中國科學院計算所獲得博士學位，現為內蒙古大學計算機學院教授、博士生導師，CCF高級會員，主要研究領域為無線網絡，下一代互聯網等。

LIU Jing was born in 1981.He received the Ph.D.degree in computer science from Institute of Computing Technology,Chinese Academy of Sciences in 2011.Now he is an associated professor at Inner Mongolia University,and the senior member of CCF.His research interests include software verification and testing,Web service technology and cloud computing,etc.

劉靖（1981—），男，內蒙古呼和浩特人，2011年于中國科學院計算所獲得博士學位，現為內蒙古大學計算機學院副教授，CCF高級會員，主要研究領域為軟件驗證與測試，Web服務技術，云計算等。

ZHANG Yujun was born in 1976.He received the Ph.D.degree in computer science from Institute of Computing Technology,Chinese Academy of Sciences in 2004.Now he is a professor and Ph.D.supervisor at Institute of Computing Technology,Chinese Academy of Sciences,and the senior member of CCF.His research interests include future Internet architecture and trusted Internet,etc.

張玉軍（1976—），男，河北衡水人，2004年于中國科學院計算所獲得博士學位，現為中國科學院計算所研究員、博士生導師，CCF高級會員，主要研究領域為未來互聯網體系結構，可信網絡等。

LI Zhongcheng was born in 1962.He received the Ph.D.degree in computer science from Institute of Computing Technology,Chinese Academy of Sciences in 1991.Now he is a professor and Ph.D.supervisor at Institute of Computing Technology,Chinese Academy of Sciences,and the senior member of CCF.His research interest is computer networks.

李忠誠（1962—），男，山東牟平人，1991年于中國科學院計算所獲得博士學位，現為中國科學院計算所研究員、博士生導師，CCF高級會員，主要研究領域為計算機網絡。

Space-Limited Storage Protocol forAutonomous Mobile Cloud*

CUI Bo1,2,LI Ru1+,LIU Jing1,ZHANG Yujun2,LI Zhongcheng2
1.College of Computer Science,Inner Mongolia University,Hohhot 010021,China
2.Network Technology Research Center,Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China
+Corresponding author:E-mail:csliru@imu.edu.cn

Concerning the scenario of localized geographical area,the autonomous mobile cloud is capable of providing provisional storage services for cloud users.However,because of the limitation of storage space in mobile nodes, maintaining the data persistence becomes more difficult.This paper proposes a space-limited storage protocol for autonomous mobile cloud named as SLAMS protocol.The central idea of this protocol is thatKcopies for each data block are kept via periodic communications among mobile nodes,and data block copies are stored into nodes with larger free storage space.This paper presents the specific data copy maintaining mechanism,corresponding data structures and algorithms,and detailed design of SLAMS protocol,respectively.The simulation results show that,compared with current major solution Phoenix,the data lost rate can be reduced by up to 50%,the time of convergence can be reduced by up to 95%,and the overhead of data block storage can be reduced by up to 90%in the SLAMS protocol.Besides,the SLAMS protocol can effectively increase the probability ofKcopies by up to 40%for each data block in case that mobile nodes have limited storage space.

autonomous mobile cloud;storage service;data copy maintenance;data loss rate

10.3778/j.issn.1673-9418.1512047

A

TP393

*The National Natural Science Foundation of China under Grant Nos.61363079,61262017,61402446,61173133,61362011(國家自然科學基金);the National Basic Research Program of China under Grant No.2012CB315804(國家重點基礎研究發展計劃(973計劃));the Research Project of Higher Education of Inner Mongolia Autonomous Region under Grant No.NJZY16020(內蒙古自治區教育廳高校科研項目).

Received 2015-12,Accepted 2016-04.

CNKI網絡優先出版:2016-04-19,http://www.cnki.net/kcms/detail/11.5602.TP.20160419.1144.014.html

CUI Bo,LI Ru,LIU Jing,et al.Space-limited storage protocol for autonomous mobile cloud.Journal of Frontiers of Computer Science and Technology,2017,11(2)：271-285.