有限空间下的自治移动云存储协议*

崔 波，李 茹，刘 靖，张玉军，李忠诚

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.