Research On Several Topology Issues In Wireless Sensor Networks Based On The Graph Related Theories

As one of the technologies that enable human sense the physical world, the technology of wireless sensor network (WSN) is suffering fast development and plays important role in the people’s daily life as well as in the field of military, industrial manufacture, environment monitor, healthcare, etc. WSN is one of the core enabling technologies in the Internet of Things. By combining with other different technologies like the mobile Internet and cloud computing, WSN and related technologies have generated a much higher cooperative economic benefits and social benefits than themselves.WSN is combined by energy and hardware constrained sensor nodes. Different from wired networks and traditional wireless networks, there isn’t complicated network management device in WSN, and the data is transmitted via wireless linkage between sensor nodes. These wireless linkages constitute the topology of WSN, and the organization, management, maintenance of the topology can only be realized by the cooperation of sensor nodes rather than the complicated network management devices. Thus, in order to reduce the cost of sensor nodes in organizing and manintaining the network topology, it is important to design and realize a scientific network topology, as well as high efficiency topology management and maintenance method. The topology of WSN has the features of self-organization, dynamic, and the sensor nodes have the energy and hardware constraints. So the topology issue in WSN is a fusion and interdiscipline research topic with the application background of network. Related research involves graph related theories, operation and optimization theories, fuzzy control theories, etc.Based on the graph related theories, this dissertation studies several topology management issues in WSN. The goal of this study is to prolong the network lifetime without major influence on the communication related performance. Based on this, several network topology models are proposed in this dissertation, the features of different network topologies are studied. And following the above work, the study gives corresponding topology management algorithms, which is proved to be energy-efficient by analysis and simulation. The proposed models can provide theoretical support to develop new topology and management schemes for WSN. The presented topology management algorithms can be the technique basis of developing new network protocols. The innovation points in this dissertation are listed as follows:(1) From the viewpoint of graph, this dissertation first systemically and clearly proposed hypergraph topology model and cluster-tree-like topology model that are adaptable to WSN. The work gives a general algorithm to use hypergraph model to develop WSN topology structure. Analysis the coverage, reliability, and energy consumption condition for different network topologies, and corresponding conclusions are given. The dissertation also presents the concept of "coverage cost of node failure", which can be used to evaluate the importance of node in the topology, and it establishes the mapping relationship between reliability and coverage.(2) Based on the WSN hypergraph topology model and hierarchical idea, for the sensor network that combined by fixed nodes, H-CEA algorithm and M-CEA algorithm are proposed which can realize the node clustering and network auto-organization, they work for the network topology formation and data transmission. In H-CEA, nodes are clustered by establishing hyperedge, and the hyperedges are connected via connecting hyperedge or intermediary node. M-CEA is the improvement of H-CEA on the aspect of distribution of cluster head nodes that makes it more uniform.(3) Based on the WSN cluster-tree-like topology model and hierarchical idea, INTRA-H algorithm and INTER-H algorithm are proposed in this dissertation. Separately, they are the topology management algorithms for the network with node mobile in the same subnet or between neighbor subnets. INTRA-H ensures the integrity and continuity of data transmission topology. And INTER-H can realize the same aim in the inter-PAN scenario, and further more it reduces the topology management and control messages which are generated in the cases of ping-pang handoff.