The Modeling And Analysis For The Novel Virtual Backbone In Wireless Sensor Networks

Wireless sensor network（WSN）is a kind of multi-hops and self-organizing network,which consists of lots of wireless sensor nodes.Once the wireless nodes in a WSN are deployed on an application area,they organize an unattended communication network autonomously without any predefined infrastructure,which causes that WSNs have widely been applied to extreme environment such as battlefield surveillance,disaster recuse,volcano monitoring and so on.However,the issues related to lifetime and data transmission in WSNs are highly challenging due to the inherent constraints on processing ability,battery energy and data transmission mechanism.Thus,in order to reduce signal conflict and interference and improve energy consumption efficiency in the process of communication,the concept of virtual backbone（VB）has been proposed to undertake routing related tasks and manage information of the whole network for extending network life and improving communication quality.In the investigation of VBs in WSNs,the size of a VB is naturally an important index to measure its performance.However,with the development of applications on WSNs,it calls for further requirements on the characteristics of VBs,such as robustness,fault-tolerance,routing overhead,diagnosability and so on.A VB with both size and order characteristics may be more suitable for practical application scenarios.In this paper,such kind of VBs is called by novel VB.Fortunately,among novel VBs,there have been some researches on approximation-constructing algorithms for the VBs with node fault-tolerance or routing cost,however,few achievements has been made on approximation-constructing algorithms for the VBs with robustness,edge fault-tolerance,diagnosability or other characteristics.This paper studies the construction of three types of novel VBs in WSNs,and the research results are as follows:Firstly,the problem of VBs construction in the WSNs with unstable transmission range has been studied.In order to obtain a VB with higher robustness to resist the instability of node transmission radius,the concept of d-robust connected dominating set is proposed for the first time in this paper,and a new evaluation index,robustness degree,is introduced.In this paper,we prove that the problem on the construction of d-robust connected dominating set in a unit disk graph is equal to that on the construction of connected dominating set in a quasi unit disk graph,and two algorithms,LLZ19-1 and LLZ19-2,are proposed.LLZ19-1 has a simple structure and good performance in terms of size in simulation,and LLZ19-2 is an approximation algorithm with approximation ratio40.68/（1-d）²+10.17,which is the first approximation algorithm for the construction of d-robust dominating set.Secondly,the problem of the VBs with edge fault-tolerance in WSNs has been studied.In this paper,we propose the concept of 2-edge connected 2-edge dominating set（（2,2）-ECDS）,and design the first approximation algorithm LLZ20 for this problem in homogeneous WSNs,where the approximation ratio of LLZ20 is 30.51.Furthermore,the problem has been generalized,that is,how to construct the VBs with edge fault tolerance in the WSNs with multiple communication modes.To solve this problem,the concept of multiple disk graph（p-MDG）is proposed for the first time to abstract the WSN with multiple communication modes in this paper.The problem of constructing VB with edge fault tolerance in a WSN with multiple communication modes is equal to that of constructing the（k,m）-ECDS in p-MDG,and an approximation algorithm LLZ21 with approximation ratio 5^（k-1）×（m+2）×max{5p/m,1}is proposed.Finally,the construction of the VBs with t-diagnosable structure in homogeneous WSNs is studied.It is the first time to study the problem of constructing the VBs with fault diagnosis structure in homogeneous WSNs.In this paper,this problem is transformed into the t-diagnosable connected dominating set（t-DCDS）problem in unit disk graph,and the first approximation algorithm LLZ22 is proposed for this problem in the case of t=2.The approximation ratio of the algorithm is 39.597+9 ln 5.To sum up,this paper conducts researches on the construction of robust VBs in the WSNs with unstable transmission radius,the construction of edge fault tolerance VBs in homogeneous WSNs,the construction of edge fault tolerance VBs in the WSNs with multiple communication modes and the construction of t-diagnosable VBs in homogeneous WSNs.Furthermore,approximation algorithms are proposed for the above problem.Through mathematical analysis and simulation experiments,the correctness and effectiveness of all algorithms proposed in this paper are proved and verified.The research results of this paper have important theoretical value on the development of communication theory and mobile computing theory.In terms of practical value,it is of great significance to the expansion of Internet and information monitoring for related networks（such as power grid,social network,transportation network,etc.）.