基于干扰模型的无线网络CDS构造算法研究
|
摘要
21世纪是信息时代,而且网络在日常生活中越来越常见。为了满足更多的需求,无线网络应运而生。但是由于无线网络的特点,使得网络中的能量是一个非常重要的资源。因此,为了节省网络中的能量、延长网络寿命,许多学者提出通过构造一个虚拟骨干网来对网络进行拓扑控制,进而实现无线网络的可扩展性和高效性。虚拟骨干网可以简化网络中的路由,将网络中的通信限制在重要的链路上,极大地减少了节点的能量消耗。
构建虚拟骨干网的技术有很多,本文主要是采用连通控制集(CDS)技术,它是实现层次型拓扑控制的技术之一并且目前是国内外研究的重点问题之一。给定一个图G=(V,E),其中V是G中节点的集合,E是边的集合,那么图G的一个控制集是子集V'(?)V,使得V中的节点要么属于V',要么是V'中节点的一跳邻居。图的连通控制集是指由控制集V'所导出的子图是连通的。
但是随着CDS构造算法研究的深入,我们在考虑时不再仅仅考虑网络节能方面。当网络处于活动状态时,一些节点在传输数据时有可能会影响其他节点接收数据。如果一个节点的一个邻居在某时刻传输数据,那么该节点在同一时刻就不能正确的从它的邻居中接收到数据。这种节点的相互之间的影响就称为干扰。干扰是无线网络中的常见现象,影响包括能量消耗、吞吐量、网络寿命在内的网络性能。拓扑控制的最初目标之一就是减少干扰,因此可以通过拓扑控制达到节能和减少干扰的双层目标。本文以现存的CDS算法为基础,添加干扰因素并设计不同干扰模型下具有不同性能的连通控制集算法。同时本文对算法进行了理论分析并利用仿真实验证明了结果的正确性。
本文共包括五部分。第一章对无线网络作了简单的介绍,给出了本课题的研究背景及意义并分析了目前的研究现状。第二章对现存的干扰模型进行了详细的描述,并给出了它们的优缺点。第三章详细介绍了在最大边干扰负载模型下,依靠节点优先级排序来构造网络的连通控制集的算法。在第四章中利用四种基本的干扰模型,给出了一种新的干扰模型并在此基础上提出了一个新的干扰感知的CDS构建算法。第五章对全文进行了总结并对下一步的工作提出了设想。
The21st century is the era of information, and the network is becoming more and more usual in normal life. So in order to meet additional demands, the wireless network came into being. However, due to the characteristics of wireless networks, energy is a very important resource in the network. Therefore, in order to save energy in the network and prolong the network lifetime, many scholars have proposed to construct a virtual backbone to control network topology. So the scalability and efficiency of the wireless network is guaranteed. The virtual backbone can simplify the routing in the network, and then the communications in the network are limited to some important links. The virtual backbone greatly reduces the energy consumption of nodes.
There are multiple technologies to build a virtual backbone, and in this paper we use the connected dominating set (CDS) which is one of the hierarchical topology control technologies. CDS is currently one of the focuses of the studies all around the world. Given a graph G=(V,E) consisting of a set of vertices V and a set of edges E, then a dominating set of the graph G is a subset V'(?)V so that a vertex in V is either in V' or is a one-hop neighbor of vertices in V'. Accordingly, a node in a network is either a dominator or a dominatee. Thus a connected dominating set of a graph is that any pair of vertices in V' is connected by at least a path in the resulting sub-graph.
During the depth of the research of CDS, what we consider is not only the energy efficiency. Transmitting nodes may affect the ability of other nodes to receive data. A node is not able to receive data from its neighbor if another neighbor is transmitting at the same time. This mutual disturbance of communication is called interference. Interference is very common in wireless networks. Interference can degrade the performances of wireless networks, including energy consumption, network throughput, network lifetime and other aspects. Reducing interference is consequently considered as one of the foremost goals of topology control. Therefore by means of topology control, the energy conservation and the reduction of interference can both be achieved. Based on the existing CDS algorithms, in this paper we take the interference into consideration and design different CDS algorithms with different interference models. Meanwhile we use the graph theory, mathematics and so on to theoretically analyze the algorithms and use simulations to show the correctness of the results.
This paper consists of five chapters. The first chapter briefly introduces the wireless network, gives the background and significance of the subject and analyzes the current research status. The second chapter describes the existing interference models in detail and gives the advantages and disadvantages of them. Based on the maximum edge interference model, in Chapter three we construct the CDS by ranking the nodes. Chapter four uses four basic interference models to propose a new interference model and using this new model design an interference aware CDS algorithm. Chapter five summarizes the whole paper and presents the future work.
构建虚拟骨干网的技术有很多,本文主要是采用连通控制集(CDS)技术,它是实现层次型拓扑控制的技术之一并且目前是国内外研究的重点问题之一。给定一个图G=(V,E),其中V是G中节点的集合,E是边的集合,那么图G的一个控制集是子集V'(?)V,使得V中的节点要么属于V',要么是V'中节点的一跳邻居。图的连通控制集是指由控制集V'所导出的子图是连通的。
但是随着CDS构造算法研究的深入,我们在考虑时不再仅仅考虑网络节能方面。当网络处于活动状态时,一些节点在传输数据时有可能会影响其他节点接收数据。如果一个节点的一个邻居在某时刻传输数据,那么该节点在同一时刻就不能正确的从它的邻居中接收到数据。这种节点的相互之间的影响就称为干扰。干扰是无线网络中的常见现象,影响包括能量消耗、吞吐量、网络寿命在内的网络性能。拓扑控制的最初目标之一就是减少干扰,因此可以通过拓扑控制达到节能和减少干扰的双层目标。本文以现存的CDS算法为基础,添加干扰因素并设计不同干扰模型下具有不同性能的连通控制集算法。同时本文对算法进行了理论分析并利用仿真实验证明了结果的正确性。
本文共包括五部分。第一章对无线网络作了简单的介绍,给出了本课题的研究背景及意义并分析了目前的研究现状。第二章对现存的干扰模型进行了详细的描述,并给出了它们的优缺点。第三章详细介绍了在最大边干扰负载模型下,依靠节点优先级排序来构造网络的连通控制集的算法。在第四章中利用四种基本的干扰模型,给出了一种新的干扰模型并在此基础上提出了一个新的干扰感知的CDS构建算法。第五章对全文进行了总结并对下一步的工作提出了设想。
The21st century is the era of information, and the network is becoming more and more usual in normal life. So in order to meet additional demands, the wireless network came into being. However, due to the characteristics of wireless networks, energy is a very important resource in the network. Therefore, in order to save energy in the network and prolong the network lifetime, many scholars have proposed to construct a virtual backbone to control network topology. So the scalability and efficiency of the wireless network is guaranteed. The virtual backbone can simplify the routing in the network, and then the communications in the network are limited to some important links. The virtual backbone greatly reduces the energy consumption of nodes.
There are multiple technologies to build a virtual backbone, and in this paper we use the connected dominating set (CDS) which is one of the hierarchical topology control technologies. CDS is currently one of the focuses of the studies all around the world. Given a graph G=(V,E) consisting of a set of vertices V and a set of edges E, then a dominating set of the graph G is a subset V'(?)V so that a vertex in V is either in V' or is a one-hop neighbor of vertices in V'. Accordingly, a node in a network is either a dominator or a dominatee. Thus a connected dominating set of a graph is that any pair of vertices in V' is connected by at least a path in the resulting sub-graph.
During the depth of the research of CDS, what we consider is not only the energy efficiency. Transmitting nodes may affect the ability of other nodes to receive data. A node is not able to receive data from its neighbor if another neighbor is transmitting at the same time. This mutual disturbance of communication is called interference. Interference is very common in wireless networks. Interference can degrade the performances of wireless networks, including energy consumption, network throughput, network lifetime and other aspects. Reducing interference is consequently considered as one of the foremost goals of topology control. Therefore by means of topology control, the energy conservation and the reduction of interference can both be achieved. Based on the existing CDS algorithms, in this paper we take the interference into consideration and design different CDS algorithms with different interference models. Meanwhile we use the graph theory, mathematics and so on to theoretically analyze the algorithms and use simulations to show the correctness of the results.
This paper consists of five chapters. The first chapter briefly introduces the wireless network, gives the background and significance of the subject and analyzes the current research status. The second chapter describes the existing interference models in detail and gives the advantages and disadvantages of them. Based on the maximum edge interference model, in Chapter three we construct the CDS by ranking the nodes. Chapter four uses four basic interference models to propose a new interference model and using this new model design an interference aware CDS algorithm. Chapter five summarizes the whole paper and presents the future work.
引文
[1]陈林星,曾曦,曹毅.移动Ad Hoc网络—自组织分组无线网络技术[M].北京：电子工业出版社,2006.
[2]D. Cullar, D. Estrin, M. Strvastava. Overview of Sensor Network [J]. Computer,2004,37(8):41-49.
[3]I.F. Akyildiz, X.D. Wang, W.L. Wang. Wireless mesh networks:a survey [J]. Computer Networks,2005,47(4):445-487.
[4]P. Santi. Topology control in wireless Ad Hoc and sensor networks [J]. ACM Computing Surveys (CSUR),2005,37(2).
[5]A. Ephremides, J.E. Wieselthier, D.J. Baker. A design concept for reliable mobile radio networks with frequency hopping signaling [C]. In Proc. of IEEE,1987,75(1):56-73.
[6]M.L. Garey, D.S. Johnson. Computers and Intractability:A guide to the theory of NP-completeness [M]. Freeman, San Francisco,1978.
[7]周新莲,吴敏,徐建波BPEC:无线传感器中一种能量感知的分布式分簇算法[J].计算机研究与发展,2009,46(5)：723-730.
[8]M. Burkhart, P. Rickenbach, R. Wattenhofer, A. Zollinger. Does topology control reduce interference?[C]. In Proc. of the5th ACM Int. Symposium on Mobile Ad-hoc Networking and Computing (MobiHoc),2004.9-19.
[9]J. LEE, B. MANS. Energy-efficient virtual backbones for reception-aware MANET [C]. In Proc. of Vehicular Technology Conference,2006,3:1097-1101.
[10]S. Guha, S. Khuller. Approximation algorithms for connected dominating sets [J]. Algorithmica,1998,20(4):374-387.
[11]X.L. Guo et al.一种新的自组网极小连通支配集生成算法[J].计算机技术与发展,2007,17(7)：17-20.
[12]李云,傅秀芬,何杰光,林茜卡.求极大独立集的程序实现研究[J].计算机技术与发展,2008,18(9)：64-67.
[13]Y.S. Li et al. On greedy construction of connected dominating sets in wireless networks [J]. WCMC,2005,5(8):927-932.
[14]M. Min, H. Du, X. Jia, C. X. Huang, S. C.-H. Huang, and W Wu, Improving construction for connected dominating set with steiner tree in wireless sensor networks, Journal of Global Optimization,2006(35):111-119.
[15]L.C. Bao et al. Stable energy-aware topology management in Ad Hoc networks [J]. Ad Hoc Networks,2010,8(3):313-327.
[16]赵学锋,杨海斌,张贵仓.基于堆的最小连通支配集高效近似算法[J].计算机工程,2011,37(2)：54-56.
[17]解文斌,李佳,鲜明,陈永光.基于拓扑特性的分布式虚拟骨干网算法[J].软件学报,2010,21(6)：1416-1425.
[18]Y. Wang and X. Li. Localized construction of bounded degree and planar spanner for wireless Ad Hoc networks[J]. Mobile Networks and Applications,2006,11(2).
[19]张信明,刘琼,代仕芳,刘永振.移动Ad Hoc网络通信量相关干扰感知路由协议[J].软件学报,2009,20(10)：2721-2728.
[20]P. Rickenbach, S. Schmid, R. Wattenhofer, A. Zollinger. A robust interference model for wireless ad-hoc networks[C]//IPDPS'05,2005.
[21]P. Gupta, P.R. Kumar. The capacity of wireless networks [J]. IEEE Transactions on Information Theory,2000,46(2):388-404.
[22]刘永振.无线自组织网络干扰模型和控制的研究[D].安徽：中国科学技术大学,2009.
[23]Gupta P and Kumar P.R. The capacity of wireless networks [J]. IEEE Transactions on Information Theory,2000,46(2):388-404.
[24]Scheideler C, W.Richa A, Santi P.2008. An O(log n) Dominating Set Protocol for Wireless AdHoc Networks under the Physical Interference Model. In Proc. Of ACM MobiHoc'08.
[25]Kim TS, Lim H, Hou JC. Improving spatial reuse through tuning transmit power, carrier sense threshold, and data rate in Multihop wireless networks. In Proc. of the ACM MobiCom,2006.366-377.
[26]Maniezzo D, Cesana M, Gerla M. IA-MAC:Interference aware MAC for WLANs. Technical Report,020037, UCLA ComputerScience Department,2002.
[27]Von P. Rickenbach, R. Wattenhofer, A. Zollinger. Algorithmic Models of Interference in Wireless Ad Hoc and Sensor Networks [J]. IEEE/ACM TRANSACTIONS ON NETWORKING,2009,17(1).
[28]D. Mirela, J. Nagesh. Distributed construction of low-interference spanners [J]. Distrib. Comput.,2009,22:15-28.
[29]Y.X. He, Y.Y. Zeng. Topology Control in wireless Sensor Networks with Interference Consideration [C]. In:Intelligent Control and Automation,2006,344:202-206.
[30]K. Alzoubi, P. J. Wan, O. Frieder. New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks [C]. In Proc. of the35th Hawaii Int'1Conf (HICSS'02),2002.3881-3887.
[31]M. Fussen, R. Wattenhofer, A. Zollinger. Interference arises at the receiver[C]. In Proc. of the Int. Conf. Wireless Networks, Communications, and Mobile Computing (Wireless COM 2005),2005.
[32]Trac N. Nguyen, Dung T. Huynh. Minimum Interference Planar Geometric Topology in Wireless Sensor Networks [C]. In:Wireless Algorithms, Systems, and Applications,2009,5682:149-158.
[33]K. Moaveni-Nejad, X.Y. Li. Low-Interference Topology Control for Wireless Ad Hoc Networks [J]. Ad Hoc&Sensor Wireless Networks,2005,1:41-64.
[34]J. Tomas et al. Reducing Interference in Ad Hoc Networks through Topology Control [C]. In Proc. of DIALM-POMC'05,2005.17-23.
[35]G.N. Feng, P.Y. Fan et al. Interference minimum network topologies for Ad Hoc networks [J]. Wireless Communications and Mobile Computing,2010,12(6):529-544.
[36]G. Calinescu, S. Tongngam. Interference-aware broadcast scheduling in wireless networks [J]. Ad Hoc Networks,2011,9(7):1069-1082.
[37]T. Moscibroda, R. Wattenhofer, Y. Weber. Protocol design beyond graph-based models [C]. In Proc. of the5th Workshop on Hot Topics in Networks (Hot Nets),2006.
[38]T. Moscibroda, R. Wattenhofer. The complexity of connectivity in wireless networks [C]. In Proc. of the25th IEEE International Conference on Computer Communications (INFOCOM),2006.1-13.
[39]O. Goussevskaia, T. Moscibroda, R. Wattenhofer. Local broadcasting in the physical interference model [C]. In:ACM SIGACT-SIGOPT International Workshop on Foundations of Mobile Computing (DialM-POMC),2008.
[40]Z. Chen, C. Qiao, J. Xu, T. Lee. A constant approximation algorithm for interference aware broadcast in wireless networks [C]. In:IEEE INFOCOM,2007.740-748.
[41]K.D. Wu, W. Liao. On Constructing Low Interference Topology in Multihop Wireless Networks [C]. In Proc. of ICC'06,2006,8:3759-3764.
[2]D. Cullar, D. Estrin, M. Strvastava. Overview of Sensor Network [J]. Computer,2004,37(8):41-49.
[3]I.F. Akyildiz, X.D. Wang, W.L. Wang. Wireless mesh networks:a survey [J]. Computer Networks,2005,47(4):445-487.
[4]P. Santi. Topology control in wireless Ad Hoc and sensor networks [J]. ACM Computing Surveys (CSUR),2005,37(2).
[5]A. Ephremides, J.E. Wieselthier, D.J. Baker. A design concept for reliable mobile radio networks with frequency hopping signaling [C]. In Proc. of IEEE,1987,75(1):56-73.
[6]M.L. Garey, D.S. Johnson. Computers and Intractability:A guide to the theory of NP-completeness [M]. Freeman, San Francisco,1978.
[7]周新莲,吴敏,徐建波BPEC:无线传感器中一种能量感知的分布式分簇算法[J].计算机研究与发展,2009,46(5)：723-730.
[8]M. Burkhart, P. Rickenbach, R. Wattenhofer, A. Zollinger. Does topology control reduce interference?[C]. In Proc. of the5th ACM Int. Symposium on Mobile Ad-hoc Networking and Computing (MobiHoc),2004.9-19.
[9]J. LEE, B. MANS. Energy-efficient virtual backbones for reception-aware MANET [C]. In Proc. of Vehicular Technology Conference,2006,3:1097-1101.
[10]S. Guha, S. Khuller. Approximation algorithms for connected dominating sets [J]. Algorithmica,1998,20(4):374-387.
[11]X.L. Guo et al.一种新的自组网极小连通支配集生成算法[J].计算机技术与发展,2007,17(7)：17-20.
[12]李云,傅秀芬,何杰光,林茜卡.求极大独立集的程序实现研究[J].计算机技术与发展,2008,18(9)：64-67.
[13]Y.S. Li et al. On greedy construction of connected dominating sets in wireless networks [J]. WCMC,2005,5(8):927-932.
[14]M. Min, H. Du, X. Jia, C. X. Huang, S. C.-H. Huang, and W Wu, Improving construction for connected dominating set with steiner tree in wireless sensor networks, Journal of Global Optimization,2006(35):111-119.
[15]L.C. Bao et al. Stable energy-aware topology management in Ad Hoc networks [J]. Ad Hoc Networks,2010,8(3):313-327.
[16]赵学锋,杨海斌,张贵仓.基于堆的最小连通支配集高效近似算法[J].计算机工程,2011,37(2)：54-56.
[17]解文斌,李佳,鲜明,陈永光.基于拓扑特性的分布式虚拟骨干网算法[J].软件学报,2010,21(6)：1416-1425.
[18]Y. Wang and X. Li. Localized construction of bounded degree and planar spanner for wireless Ad Hoc networks[J]. Mobile Networks and Applications,2006,11(2).
[19]张信明,刘琼,代仕芳,刘永振.移动Ad Hoc网络通信量相关干扰感知路由协议[J].软件学报,2009,20(10)：2721-2728.
[20]P. Rickenbach, S. Schmid, R. Wattenhofer, A. Zollinger. A robust interference model for wireless ad-hoc networks[C]//IPDPS'05,2005.
[21]P. Gupta, P.R. Kumar. The capacity of wireless networks [J]. IEEE Transactions on Information Theory,2000,46(2):388-404.
[22]刘永振.无线自组织网络干扰模型和控制的研究[D].安徽：中国科学技术大学,2009.
[23]Gupta P and Kumar P.R. The capacity of wireless networks [J]. IEEE Transactions on Information Theory,2000,46(2):388-404.
[24]Scheideler C, W.Richa A, Santi P.2008. An O(log n) Dominating Set Protocol for Wireless AdHoc Networks under the Physical Interference Model. In Proc. Of ACM MobiHoc'08.
[25]Kim TS, Lim H, Hou JC. Improving spatial reuse through tuning transmit power, carrier sense threshold, and data rate in Multihop wireless networks. In Proc. of the ACM MobiCom,2006.366-377.
[26]Maniezzo D, Cesana M, Gerla M. IA-MAC:Interference aware MAC for WLANs. Technical Report,020037, UCLA ComputerScience Department,2002.
[27]Von P. Rickenbach, R. Wattenhofer, A. Zollinger. Algorithmic Models of Interference in Wireless Ad Hoc and Sensor Networks [J]. IEEE/ACM TRANSACTIONS ON NETWORKING,2009,17(1).
[28]D. Mirela, J. Nagesh. Distributed construction of low-interference spanners [J]. Distrib. Comput.,2009,22:15-28.
[29]Y.X. He, Y.Y. Zeng. Topology Control in wireless Sensor Networks with Interference Consideration [C]. In:Intelligent Control and Automation,2006,344:202-206.
[30]K. Alzoubi, P. J. Wan, O. Frieder. New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks [C]. In Proc. of the35th Hawaii Int'1Conf (HICSS'02),2002.3881-3887.
[31]M. Fussen, R. Wattenhofer, A. Zollinger. Interference arises at the receiver[C]. In Proc. of the Int. Conf. Wireless Networks, Communications, and Mobile Computing (Wireless COM 2005),2005.
[32]Trac N. Nguyen, Dung T. Huynh. Minimum Interference Planar Geometric Topology in Wireless Sensor Networks [C]. In:Wireless Algorithms, Systems, and Applications,2009,5682:149-158.
[33]K. Moaveni-Nejad, X.Y. Li. Low-Interference Topology Control for Wireless Ad Hoc Networks [J]. Ad Hoc&Sensor Wireless Networks,2005,1:41-64.
[34]J. Tomas et al. Reducing Interference in Ad Hoc Networks through Topology Control [C]. In Proc. of DIALM-POMC'05,2005.17-23.
[35]G.N. Feng, P.Y. Fan et al. Interference minimum network topologies for Ad Hoc networks [J]. Wireless Communications and Mobile Computing,2010,12(6):529-544.
[36]G. Calinescu, S. Tongngam. Interference-aware broadcast scheduling in wireless networks [J]. Ad Hoc Networks,2011,9(7):1069-1082.
[37]T. Moscibroda, R. Wattenhofer, Y. Weber. Protocol design beyond graph-based models [C]. In Proc. of the5th Workshop on Hot Topics in Networks (Hot Nets),2006.
[38]T. Moscibroda, R. Wattenhofer. The complexity of connectivity in wireless networks [C]. In Proc. of the25th IEEE International Conference on Computer Communications (INFOCOM),2006.1-13.
[39]O. Goussevskaia, T. Moscibroda, R. Wattenhofer. Local broadcasting in the physical interference model [C]. In:ACM SIGACT-SIGOPT International Workshop on Foundations of Mobile Computing (DialM-POMC),2008.
[40]Z. Chen, C. Qiao, J. Xu, T. Lee. A constant approximation algorithm for interference aware broadcast in wireless networks [C]. In:IEEE INFOCOM,2007.740-748.
[41]K.D. Wu, W. Liao. On Constructing Low Interference Topology in Multihop Wireless Networks [C]. In Proc. of ICC'06,2006,8:3759-3764.