Connected Dominating Set In MANETs～2

MANETs (mobile ad hoc networks), composed of independent and mobile wireless nodes, aredynamic self-organized systems in which the infrastructure and central controlling entities areabsent. In MANETs, each node works both as a host and a router. These characteristics makeMANETs especially suitable for use in conference meetings, disaster relief and rescue, roofnetworks and battlefields. However, there are still some open issues in MANETs, which include 1)efficient broadcasting: as the fundamental technology of routing, broadcasting encounters problemssuch as broadcast storm and energy reservation; 2) network management: simple and well-definedmechanisms are seriously needed to guarantee collaborations between different nodes whichrandomly join and leave a network, or move inside the network in hardly predictable patterns; and3) resource locating: resource locating is the key to implement data dissemination, servicediscovery and impromptu collaboration.Backbone that fits MANET is proved to be efficient to solve these issues. In this dissertation,the dominating set theory is well studied and the recently proposed CDS (connected dominating set)construction algorithms in MANETs are analyzed. In order to resolve the problems described above,this dissertation puts forward six original algorithms based on CDS.The lifecycle of the backbone in MANETs can be summarized as CDS construction, CDSmanagement, and deployment of CDS. The contributions in this dissertation, in terms of backbonelifecycle, can be categorized as follows:1) CDS-based broadcasting algorithms in MANETs. To fulfill the requirements of differentapplications, two CDS construction algorithms, named CDSCA (connected dominating set withcircle avoidance) and ECARSP (eliminating common adjacency relation with self-pruning), arepresented.CDSCA is a MIS (maximum independent set) based CDS construction algorithm. In CDSCA,nodes interact with each other asynchronously. In the phrase of dominating nodes inter-connection,the algorithm manages to eliminate all 5 kinds of circles formed by dominating nodes, so that thecardinality of the CDS is minimized.ECARSP is a CDS construction algorithm based on neighbor designating. In ECARSP,construction packets are relayed by selected dominating nodes. In this way, the corresponding CDSis constructed on-the-fly. To reduce the cardinality of constructed CDS, ECARSP combines threetechniques, namely local uncovered nodes reduction, common adjacency relation elimination, andmultipoint relaying combined with self-pruning.2) ECARSP-based CDS maintenance algorithm (ECDSMA). ECDSMA classifies nodebehaviors into three types: join, departure, and movement. For each type of behavior, ECDSMAgives the method of CDS maintenance. According to the discussion on mobility modeling,ECDSMA can be viewed as a solution to CDS mobility management. ECDSMA takes fulladvantages of the network information gathered by ECARSP, which means nodes are not requiredto be aware of their own mobility states. Taking the methodology employed in ECARSP to adjust partial changes on the network, ECDSMA can restrict both the number of influenced nodes and theCDS cardinality.3) Deployment of CDS in MANETs. This dissertation mainly concentrates on two topics:CDS-based energy-efficient broadcasting algorithm and resource locating algorithm in MANETs.CDS-based energy-efficient broadcasting algorithm in MANETs. In the UDG model, usingMCDS as the virtual backbone of broadcasting guarantees fewer relaying nodes, while littleconsideration is taken on energy consumption of individual node. Nodes with larger number ofneighbors are prone to being drained out quickly because of more frequent packets relaying. Thus,the lifetime of the network would be short. According to the energy model of data transmission inmobile ad hoc networks and the battery-operated characteristic of mobile devices, a new metriccalled relaying efficiency was modeled to reflect the trade off between network lifetime and globalenergy consumption. Based on the remaining energy and the degree of nodes, this model considerstransmission power of different nodes and evaluates the lifetime of each node by its recent energyconsumption. Following this model, a multipoint-relaying based energy-efficient broadcastingalgorithm (EE-MPR) was proposed. By selecting the nodes with high relaying priority as relayingnodes, a broadcasting tree is constructed on the fly with smaller broadcasting cost. The energy loadis evenly distributed among the devices and the lifetime of the network is prolonged. Simulationresults showed that EE-MPR outperforms existing broadcasting algorithms in terms of lifetime ofthe network and the energy cost.Resource locating algorithm in MANETs. From the viewpoint of Peer-to-Peer computing, thisdissertation surveys the state of the art of resource locating algorithms in MANETs. Twoindex-based resource locating algorithms, namely LIT (local index tree) and DSI (dominating setindices), are proposed. In LIT, a node maintains a tree-structure index of resources on surroundingnodes, the indexing radius is dynamically adjusted and nodes moving at high speed are deletedfrom the tree. Thus only the resource metadata of stable nodes is locally indexed. In DSI, sharingnodes actively advertise their resource metadata on the CDS. Both of the algorithms can greatlyreduce the user response time.Both theoretical analysis and simulation results show that the algorithms proposed in thisdissertation outperform existing algorithms in terms of the concerned criteria.