基于稳定邻居和能量预测的移动自组网数据复制算法研究
|
摘要
移动自组网不依赖固定基础设施,具有自组织、可快速部署、环境适应力强、抗毁性强等特点,在军事战场通信、抢险救灾、紧急搜救等特殊环境中有着广泛的应用。移动自组网中的数据可用性非常低,数据复制技术作为数据管理的关键技术和提高数据可用性及系统性能的重要手段,在移动自组网中有着非常重要的应用。
由于节点的移动性、能量有限性的问题,使数据复制技术面临节点邻居的不稳定和能量消耗不均的问题。因此,面向稳定预测和能量预测方面的复制算法的研究有着重要意义。本文的主要工作包括：
第一、针对邻居节点的边缘移动和能量消耗的不公平性,提出了基于稳定邻居的数据复制(SNDR)算法。该算法对节点与邻居间的连接进行稳定性分析,计算一定时间间隔后的稳定率,通过稳定率获取节点的稳定邻居集。节点与稳定邻居共享数据资源,收集稳定邻居对数据的加权访问频度,并对访问频度总和降序排列。按照排列放置副本时,对访问频度相近的多个节点,综合考虑这些节点的剩余能量、稳定连接度和剩余存储空间,选择合适的节点放置副本。这样在减少节点边缘移动的影响同时,对节点的能量消耗进行平衡。在网络模拟器NS2中对算法进行验证,模拟实验结果表明,在移动自组网中SNDR算法能有效地提高数据的访问成功率,平衡节点间的能量消耗。
第二、针对网络中节点快速耗尽而导致部分数据难以访问的情况,提出了基于能量预测的副本调整(EPRA)算法。该算法在节点的剩余能量较少时通过剩余能量值和能量消耗率对节点的剩余生存时间进行预测,若剩余生存时间较短,在节点的邻居范围内通过数据的副本数判断节点中数据的重要性。对重要数据的复制分为邻居中有剩余存储空间、有其它数据的重复副本和没有剩余存储空间及重复副本三种情况,并考虑邻居的访问频度、剩余能量和连接度以选择合适的节点进行放置。模拟实验结果表明,在移动自组网中,部分节点快速耗尽的情况下,EPRA算法能有效提高数据的访问成功率。
Mobile ad hoc network does not rely on fixed infrastructure. Due to the features such as self-organizing, rapidly deploying, environmental adaptability and survivability, it has a wide application in military battlefield communications, disaster relief, emergency rescue and other special circumstances. The data availability in mobile ad hoc is very low. As a key technique of data management and an important method to improve data availability and system performance, data replication has an important application in mobile ad hoc network.
However, because of the movement characteristics and limited energy of nodes, the data replication technology in mobile ad hoc network faces new problems such as unstable neighbor and unbalance energy consumption. Therefore, stability prediction and energy prediction play an important role in replication algorithm. Our main works can be summarized as follows:
Firstly, according to the edge movement of neighbors and the unfairness energy consumption, a replication algorithm named SNDR is proposed based on stable neighbors. SNDR algorithm analysis the stability of the link between node and neighbor and calculates the stability ratio, then gains the stable neighbors of node. In SNDR algorithm, node shares data with stable neighbors; it collects the weighted access frequency of stable neighbors and arranges the sum of access frequency in descending order. In order to select a right node to allocate the replica, the nodes that have the similar access frequency in addition consider node's residual energy, steady connection degree and free storage space in the placing process. In this way, SDNR can not only reduce the influence of the edge movement of neighbors but also balance the energy consumption between nodes. SNDR algorithm is implemented by network simulator NS2, the simulation experiment results show that in mobile ad hoc network, SNDR algorithm can effectively improve the rate of successful data access and balance the power consumption among nodes.
Secondly, considering the situation that some data items become difficult to access after some nodes quickly exhaust the energy, a replica adjusting algorithm named EPRA is proposed based on energy prediction. When the residual energy of node is few, EPRA algorithm predicts the residual survival time of node by residual energy and the rate of energy consumption. If the residual survival time of node is short, EPRA algorithm judges the important data by the number of replicas within neighbors. In the copying process of important data, EPRA algorithm considers three situations that there are free storage spaces, there are other data's duplication, there are no free storage space and other data's duplication in neighbors, then select the right node to allocate the important data with the concern about access frequency, node's residual energy and connection degree. Simulation experiment results show that when partial nodes quickly exhaust the energy, EPRA algorithm can effectively improve the rate of successful data access.
由于节点的移动性、能量有限性的问题,使数据复制技术面临节点邻居的不稳定和能量消耗不均的问题。因此,面向稳定预测和能量预测方面的复制算法的研究有着重要意义。本文的主要工作包括：
第一、针对邻居节点的边缘移动和能量消耗的不公平性,提出了基于稳定邻居的数据复制(SNDR)算法。该算法对节点与邻居间的连接进行稳定性分析,计算一定时间间隔后的稳定率,通过稳定率获取节点的稳定邻居集。节点与稳定邻居共享数据资源,收集稳定邻居对数据的加权访问频度,并对访问频度总和降序排列。按照排列放置副本时,对访问频度相近的多个节点,综合考虑这些节点的剩余能量、稳定连接度和剩余存储空间,选择合适的节点放置副本。这样在减少节点边缘移动的影响同时,对节点的能量消耗进行平衡。在网络模拟器NS2中对算法进行验证,模拟实验结果表明,在移动自组网中SNDR算法能有效地提高数据的访问成功率,平衡节点间的能量消耗。
第二、针对网络中节点快速耗尽而导致部分数据难以访问的情况,提出了基于能量预测的副本调整(EPRA)算法。该算法在节点的剩余能量较少时通过剩余能量值和能量消耗率对节点的剩余生存时间进行预测,若剩余生存时间较短,在节点的邻居范围内通过数据的副本数判断节点中数据的重要性。对重要数据的复制分为邻居中有剩余存储空间、有其它数据的重复副本和没有剩余存储空间及重复副本三种情况,并考虑邻居的访问频度、剩余能量和连接度以选择合适的节点进行放置。模拟实验结果表明,在移动自组网中,部分节点快速耗尽的情况下,EPRA算法能有效提高数据的访问成功率。
Mobile ad hoc network does not rely on fixed infrastructure. Due to the features such as self-organizing, rapidly deploying, environmental adaptability and survivability, it has a wide application in military battlefield communications, disaster relief, emergency rescue and other special circumstances. The data availability in mobile ad hoc is very low. As a key technique of data management and an important method to improve data availability and system performance, data replication has an important application in mobile ad hoc network.
However, because of the movement characteristics and limited energy of nodes, the data replication technology in mobile ad hoc network faces new problems such as unstable neighbor and unbalance energy consumption. Therefore, stability prediction and energy prediction play an important role in replication algorithm. Our main works can be summarized as follows:
Firstly, according to the edge movement of neighbors and the unfairness energy consumption, a replication algorithm named SNDR is proposed based on stable neighbors. SNDR algorithm analysis the stability of the link between node and neighbor and calculates the stability ratio, then gains the stable neighbors of node. In SNDR algorithm, node shares data with stable neighbors; it collects the weighted access frequency of stable neighbors and arranges the sum of access frequency in descending order. In order to select a right node to allocate the replica, the nodes that have the similar access frequency in addition consider node's residual energy, steady connection degree and free storage space in the placing process. In this way, SDNR can not only reduce the influence of the edge movement of neighbors but also balance the energy consumption between nodes. SNDR algorithm is implemented by network simulator NS2, the simulation experiment results show that in mobile ad hoc network, SNDR algorithm can effectively improve the rate of successful data access and balance the power consumption among nodes.
Secondly, considering the situation that some data items become difficult to access after some nodes quickly exhaust the energy, a replica adjusting algorithm named EPRA is proposed based on energy prediction. When the residual energy of node is few, EPRA algorithm predicts the residual survival time of node by residual energy and the rate of energy consumption. If the residual survival time of node is short, EPRA algorithm judges the important data by the number of replicas within neighbors. In the copying process of important data, EPRA algorithm considers three situations that there are free storage spaces, there are other data's duplication, there are no free storage space and other data's duplication in neighbors, then select the right node to allocate the important data with the concern about access frequency, node's residual energy and connection degree. Simulation experiment results show that when partial nodes quickly exhaust the energy, EPRA algorithm can effectively improve the rate of successful data access.
引文
[1]郑少仁,王海涛,赵志峰等.Ad Hoc网络技术.人民邮电出版社,2005,54-72
[2]Perkins C E. Ad Hoc Networking. London:Addison Wesley,2001,8-23
[3]陈林星,曾曦,曹毅.移动Ad Hoc网络-自组织分组无线网络技术.电子工业出版社,2006,12-28
[4]Imrich C, Marco C, Liu J J:Mobile Ad Hoc Networking:Imperatives and Challenges. Ad Hoc Networks,2003,1(1):13-64
[5]Chakrabarthi S, Mishra A. QoS Issues in Ad Hoc Wireless Networks. Computing science Department University of Albert,2002,142-148
[6]Perich F, Joshi A, Chirkova R. Data Management for Mobile Ad-Hoc Networks. Springer Berlin Heidelberg,2006,132-176
[7]Li D M, Wang J C, Zhang L P et al. A Cooperative Location Management Scheme for Mobile Ad Hoc Networks. In:Proc of IJCNS,2009,732-741
[8]Housley et al. Http://www.ietf.org,1999-12-10
[9]Vaidaya N. The Ad Hoc Network Research Group(WNG). http://www.crhc.uiuc.edu/-nhv/,2006-08-04
[10]Gerla M. The WAM Lab. http://www.cs.ucla.edu/NRL/wireless/,2006-04-08
[11]Zygmunt J H. Wireless Networks Laboratory.http://wnl.ece.cornell.edu/, 2006-09-05
[12]The INSIGNIA QOS Framework. http://comet.columbia.edu/insignia/, 2001-11-12
[13]李芸,杨金民,张大方.无线网络中一种新的数据复制算法.计算机应用研究,2007,6(14)：94-97
[14]Sivsubramanian S, Pierre G. A Case for Dynamic Selection of Replication and Caching Strategies. In:Proc of the Eighth International Workshop on Web Content Caching and Distribution,2003,275-282
[15]JIN Y W. A Survey of Cache/Proxy for Transparent Data Replication. In:Proc of the Second International Conference on SKG'06,2006,35-40
[16]Derhab A, Badache N. Data Replication Protocols for Mobile Ad-Hoc Networks:A Survey and Taxonomy. IEEE Communications Surveys and Tutorials Journal,2009,11(2):33-51
[17]Tian K Q, Cox D C. Mobility Management in Wireless Networks:Data Replication Strategies and Applications. Kluwer Academic Publishers,2004, 7-29
[18]Hara T. Data Replication Issues in Mobile Ad Hoc Networks. In:Proc of the Sixteenth International Workshop on Database and Expert Systems Application, 2005,753-757
[19]Derhab A, Badache N, Bouabdallah A. A Partition Prediction Algorithm for Service Replication in Mobile Ad Hoc Networks. In:Proc of the Second Annual Conference on-demand Network Systems and Service,2005,236-245
[20]Guo Z H, Malakooti B. Energy Aware Proactive MANET Routing with Prediction on Energy Consumption. In:Proc of International Conference on Wireless Algorithms,Systems and Applications,2007,287-292
[21]Bartolini N, Prestiz F L, Petrioli C. Optimal Dynamic Replica Placement in Content Delivery Networks. In:Proc of ICON 2003,2003,125-130
[22]Vittoria G. Data Replication Effectiveness in Mobile Ad-Hoc Networks. In:Proc of PEWASUN'04,2004,17-22
[23]Karlsson M, Karamanolis C, Mahalingam M. A Framework for Evaluating Replica Placement Algorithms. Technical Report HPL-2002-219,2002,1-12
[24]Padmanabhan P, Gruenwald L, Vallur A et al. A Survey of Data Replication Techniques for Mobile Ad Hoc Network Databases. Journal of Very Large DataBases,2008,17(5):1143-1164
[25]Prasanna P, Le G. Managing Data Replication in Mobile Ad-Hoc Network Databases. In:Proc of International Conference on Collaborative Computing, 2006,1-10
[26]Mahmood A. Object Grouping and Replication Algorithms for World Wide Web. Informatica 29,2005,347-356
[27]Kawadia V, Kumar P R. Power Control and Clustering in Ad Hoc Networks. In: Proc of IEEE INFOCOM,2003,459-469
[28]Hara T. Effective Replica Allocation in Ad Hoc Networks for Improving Data Accessibility. In:Proc of IEEE INFOCOM,2001,1568-1576
[29]Hara T. Replica Allocation in Ad Hoc Networks with Periodic Data Update. In: Proc of the Third International Conference on Mobile Data Management,2002, 1568-1576
[30]Yin L Z, Cao G H. Balancing the Tradeoffs Between Data Accessibility and Query Delay in Ad Hoc Networks. In:Proc of IEEE Symposium on Reliable Distributed Systems,2004,289-298
[31]Hara T, Loh Y H, Nishio S. Data Replication Methods Based on the Stability of Radio Links in Ad Hoc Networks. Journal of the Information Processing Society of Japan,2003,44(9):2308-2319
[32]Wang K, Li B. Efficient and Guaranteed Service Coverage in Partitionable Mobile Ad-hoc Networks. In:Proc of IEEE Joint Conference of Computer and Communication Societies,2002,1089-1098
[33]Chen K, Shah S H, Nahrstedt K. Cross-layer Design for Data Accessibility in Mobile Ad Hoc Networks. In:Proc of the Fifth World Multiconferenceon Systemics,Cybernetics and Informatics,2001,49-76
[34]Shinohara M, Hara T, Nishio S. Data Replication Considering Power Consumption in Ad Hoc Networks. In:Proc of Mobile Data Management 2007 International Conference,2007,118-225
[35]Shinohara M, Hara T, Nishio S. Replica Allocation Considering Power Consumption in Mobile Ad Hoc Networks. In:Proc of the Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops,2006,463-467
[36]Yu G, Martin P. Cluster-based Replication for Large-scale Mobile Ad-hoc Networks. In:Proc of International Conference on Wireless Networks, Communications and Mobile Computing,2005,552-557
[37]Zheng J, Wang Y J, Lu X C et al. A Dynamic Adaptive Replica Allocation Algorithm in Mobile Ad Hoc Networks. IEEE Int'l Conf on Pervasive Computing and Communications,2004,65-70
[38]郑静,卢锡城,王意洁.移动自组网中基于分簇的数据复制算法.软件学报,2005,16(8)：1474-1483
[39]Huang J L, Chen M S, Peng W C. Exploring Group Mobility for Replica Data Allocation in a Mobile Environment. In:Proc of the Twelfth International Conference on Information and Knowledge Management,2003,161-168
[40]Shi K, Zygmunt J Haas. Quantitative Analysis of Partition Statistics and their Impact on Data Replication in MANETs. In:Proc of the Sixth International Symposium on Parallel and Distributed Computing,2007,5-8
[41]杨涛.数据网络中数据复制管理.学位论文.合肥：中国科学技术大学,2007,11-14
[42]Cheng H, Cao J N, Wang X W et al. Stability-based Multi-objective Clustering in Mobile Ad Hoc Networks. In:Proc of QShine'06,2006,191(27):1-8
[43]方路平,刘世华,陈盼等.NS-2网络模拟基础与应用.国防工业出版社,2008,2-20
[44]Hogie L. An Overview of MANETs Simulation. In:Proc of the First International Workshop on MTCoord 2005,2006,150(1):81-101
[45]唐艳芬.Ad Hoc网络基于能量预测的多径路由协议研究.学位论文.长沙：湖南大学,2007,30-34
[2]Perkins C E. Ad Hoc Networking. London:Addison Wesley,2001,8-23
[3]陈林星,曾曦,曹毅.移动Ad Hoc网络-自组织分组无线网络技术.电子工业出版社,2006,12-28
[4]Imrich C, Marco C, Liu J J:Mobile Ad Hoc Networking:Imperatives and Challenges. Ad Hoc Networks,2003,1(1):13-64
[5]Chakrabarthi S, Mishra A. QoS Issues in Ad Hoc Wireless Networks. Computing science Department University of Albert,2002,142-148
[6]Perich F, Joshi A, Chirkova R. Data Management for Mobile Ad-Hoc Networks. Springer Berlin Heidelberg,2006,132-176
[7]Li D M, Wang J C, Zhang L P et al. A Cooperative Location Management Scheme for Mobile Ad Hoc Networks. In:Proc of IJCNS,2009,732-741
[8]Housley et al. Http://www.ietf.org,1999-12-10
[9]Vaidaya N. The Ad Hoc Network Research Group(WNG). http://www.crhc.uiuc.edu/-nhv/,2006-08-04
[10]Gerla M. The WAM Lab. http://www.cs.ucla.edu/NRL/wireless/,2006-04-08
[11]Zygmunt J H. Wireless Networks Laboratory.http://wnl.ece.cornell.edu/, 2006-09-05
[12]The INSIGNIA QOS Framework. http://comet.columbia.edu/insignia/, 2001-11-12
[13]李芸,杨金民,张大方.无线网络中一种新的数据复制算法.计算机应用研究,2007,6(14)：94-97
[14]Sivsubramanian S, Pierre G. A Case for Dynamic Selection of Replication and Caching Strategies. In:Proc of the Eighth International Workshop on Web Content Caching and Distribution,2003,275-282
[15]JIN Y W. A Survey of Cache/Proxy for Transparent Data Replication. In:Proc of the Second International Conference on SKG'06,2006,35-40
[16]Derhab A, Badache N. Data Replication Protocols for Mobile Ad-Hoc Networks:A Survey and Taxonomy. IEEE Communications Surveys and Tutorials Journal,2009,11(2):33-51
[17]Tian K Q, Cox D C. Mobility Management in Wireless Networks:Data Replication Strategies and Applications. Kluwer Academic Publishers,2004, 7-29
[18]Hara T. Data Replication Issues in Mobile Ad Hoc Networks. In:Proc of the Sixteenth International Workshop on Database and Expert Systems Application, 2005,753-757
[19]Derhab A, Badache N, Bouabdallah A. A Partition Prediction Algorithm for Service Replication in Mobile Ad Hoc Networks. In:Proc of the Second Annual Conference on-demand Network Systems and Service,2005,236-245
[20]Guo Z H, Malakooti B. Energy Aware Proactive MANET Routing with Prediction on Energy Consumption. In:Proc of International Conference on Wireless Algorithms,Systems and Applications,2007,287-292
[21]Bartolini N, Prestiz F L, Petrioli C. Optimal Dynamic Replica Placement in Content Delivery Networks. In:Proc of ICON 2003,2003,125-130
[22]Vittoria G. Data Replication Effectiveness in Mobile Ad-Hoc Networks. In:Proc of PEWASUN'04,2004,17-22
[23]Karlsson M, Karamanolis C, Mahalingam M. A Framework for Evaluating Replica Placement Algorithms. Technical Report HPL-2002-219,2002,1-12
[24]Padmanabhan P, Gruenwald L, Vallur A et al. A Survey of Data Replication Techniques for Mobile Ad Hoc Network Databases. Journal of Very Large DataBases,2008,17(5):1143-1164
[25]Prasanna P, Le G. Managing Data Replication in Mobile Ad-Hoc Network Databases. In:Proc of International Conference on Collaborative Computing, 2006,1-10
[26]Mahmood A. Object Grouping and Replication Algorithms for World Wide Web. Informatica 29,2005,347-356
[27]Kawadia V, Kumar P R. Power Control and Clustering in Ad Hoc Networks. In: Proc of IEEE INFOCOM,2003,459-469
[28]Hara T. Effective Replica Allocation in Ad Hoc Networks for Improving Data Accessibility. In:Proc of IEEE INFOCOM,2001,1568-1576
[29]Hara T. Replica Allocation in Ad Hoc Networks with Periodic Data Update. In: Proc of the Third International Conference on Mobile Data Management,2002, 1568-1576
[30]Yin L Z, Cao G H. Balancing the Tradeoffs Between Data Accessibility and Query Delay in Ad Hoc Networks. In:Proc of IEEE Symposium on Reliable Distributed Systems,2004,289-298
[31]Hara T, Loh Y H, Nishio S. Data Replication Methods Based on the Stability of Radio Links in Ad Hoc Networks. Journal of the Information Processing Society of Japan,2003,44(9):2308-2319
[32]Wang K, Li B. Efficient and Guaranteed Service Coverage in Partitionable Mobile Ad-hoc Networks. In:Proc of IEEE Joint Conference of Computer and Communication Societies,2002,1089-1098
[33]Chen K, Shah S H, Nahrstedt K. Cross-layer Design for Data Accessibility in Mobile Ad Hoc Networks. In:Proc of the Fifth World Multiconferenceon Systemics,Cybernetics and Informatics,2001,49-76
[34]Shinohara M, Hara T, Nishio S. Data Replication Considering Power Consumption in Ad Hoc Networks. In:Proc of Mobile Data Management 2007 International Conference,2007,118-225
[35]Shinohara M, Hara T, Nishio S. Replica Allocation Considering Power Consumption in Mobile Ad Hoc Networks. In:Proc of the Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops,2006,463-467
[36]Yu G, Martin P. Cluster-based Replication for Large-scale Mobile Ad-hoc Networks. In:Proc of International Conference on Wireless Networks, Communications and Mobile Computing,2005,552-557
[37]Zheng J, Wang Y J, Lu X C et al. A Dynamic Adaptive Replica Allocation Algorithm in Mobile Ad Hoc Networks. IEEE Int'l Conf on Pervasive Computing and Communications,2004,65-70
[38]郑静,卢锡城,王意洁.移动自组网中基于分簇的数据复制算法.软件学报,2005,16(8)：1474-1483
[39]Huang J L, Chen M S, Peng W C. Exploring Group Mobility for Replica Data Allocation in a Mobile Environment. In:Proc of the Twelfth International Conference on Information and Knowledge Management,2003,161-168
[40]Shi K, Zygmunt J Haas. Quantitative Analysis of Partition Statistics and their Impact on Data Replication in MANETs. In:Proc of the Sixth International Symposium on Parallel and Distributed Computing,2007,5-8
[41]杨涛.数据网络中数据复制管理.学位论文.合肥：中国科学技术大学,2007,11-14
[42]Cheng H, Cao J N, Wang X W et al. Stability-based Multi-objective Clustering in Mobile Ad Hoc Networks. In:Proc of QShine'06,2006,191(27):1-8
[43]方路平,刘世华,陈盼等.NS-2网络模拟基础与应用.国防工业出版社,2008,2-20
[44]Hogie L. An Overview of MANETs Simulation. In:Proc of the First International Workshop on MTCoord 2005,2006,150(1):81-101
[45]唐艳芬.Ad Hoc网络基于能量预测的多径路由协议研究.学位论文.长沙：湖南大学,2007,30-34