Connectivity, Strong Orientation Of Graphs And Wireless Sensor Networks

Graph theory is a very popular area of discrete mathematics with not only numerous theoretical developments, but also countless applications to practical problems, such as, chemistry, biology, computer science, communication networks. This thesis is mainly about the strong orientation and the optimal strong (κ,d)-orientation of graphs, and some applications in wireless sensor networks.A wireless sensor network (WSN) is a wireless network comprised of a large number of sensor nodes which are deployed randomly. Wireless sensor networks have attracted a good deal of research attention as they used in many application areas, including battlefield surveillance, environment and habitat monitoring, home automation, inventory tracking, and healthcare application [56].In wireless sensor networks, energy source is usually battery cell, which is impossible to recharge while WSNs are working. Therefore, one of the main issues in wireless sensor networks is how to prolong the network lifetime of WSNs with certain energy source as well as how to maintain coverage and connectivity.We address an application which monitors a set of targets with known locations.A large number of sensor nodes are dispersed randomly in close proximity to the set of targets, and send the monitored information to one or more central proceeding nodes. An efficient method to extend the wireless sensor network lifetime is splitting the sensor nodes into a maximal number of disjoint sets each of which completely covers all the targets and send the monitored information to the central proceeding nodes, and the sets are activated successively. Only the sensor nodes from the active sets are responsible for monitor all the targets as well as each activated set remains connected for data collection. We consider throe different models for this application.1. Suppose that each sensor nodes monitors exact one target. We present this model as the disjoint sets coverage and connectivity (DSCC) problem, and prove it is NP-complete. And we design an approximate algorithm and present an efficient implementation of heuristic functions for this algorithm. Theoretical analysis and experimental evaluations are also given.2. Suppose the wireless sensor networks satisfying that some nodes each of which monitors one target and transfers information, the others just for connection. Assume the wireless sensor network hasιtargets, and each is monitored by k sensor nodes. We show if k=2 and the graph G corresponding to the wireless sensor network is (ι+max{1,ι-4})-connected, or k > 3 and G is (ι(k-1)+1)-connected, then we can find A; (the maximum number) disjoint sets each of which completely covers all the targets and remains connected to one of the central processing nodes. These disjoint sets are activated successively, and only the sensor nodes from the active set are responsible for monitoring the targets and connectivity, all other nodes are into a sleep mode. And we also give the related algorithms to find the A; disjoint sets.3. Base on the model 2, assume the working time of the node only for connection is d times as the one both for monitoring and connection. We show that it is NP-complete to organize the nodes into maximum number of different sets, even though the network graphs satisfy some conditions of connectivity. An approximate algorithm is designed to improve the lifetime of WSNs. Theoretical analysis and experimental evaluations are also presented.It is well-known that introduction of one-way street usually decreases the number of car accidents and allows one to simplify the traffic control. Graph theoretical model of the one-way street problem can be traced back to the classical paper of Rabbins [51]. One-way street problem is a problem of orientation, in which many criteria were introduced [2, 14, 24, 34, 52, 53, 54, 55]. The definitions of strong distance, strong radius (diameter) of strong digraphs and strong oriented graphs were introduced by Chartrand et al. [9]. For two vertices u and v in a strong oriented graph D, the strong distance sd_D(u,v) between u and v is the minimum size (the number of arcs) of a strong sub-digraph of D containing u and v. For a vertex v of D, the strong eccentricity se_D(v) is the strong distance between v and a vertex farthest from v. The strong radius srad(D) (resp. strong diameter sdiam(D)) is the minimum (resp. maximum) strong eccentricity among the vertices of D. For general graph, Lai et al. [36] gave the definitions of the lower and upper orientable strong radius and diameter. The lower (resp. upper) orientable strong radius srad(G) (resp. SRAD(G)) of a graph G is the minimum (resp. maximum) strong radius over all strong orientations of G. The lower (resp. upper) orientable strong diameter sdiam(G) (resp. SDIAM(G)) of a graph G is the minimum (resp. maximum) strong diameter over all strong orientations of G. For any strong orientation D of a graph G, it satisfiesκ(D)≤[κ(G)/2] and sdiam(D)≥sdiam(G),whereκ(D) (resp.κ(G)) is the strong connectivity of D (resp. connectivity of G). Usually, not all the strong orientations of G can satisfy both of these equalities. We define the strong orientation of G satisfies both equalities as the optimal strong (κ,d)-orientation.Base on the criteria, like strong distance, strong radius (diameter), we focus on the strong distance and strong radius (diameter) in some special oriented graphs. We get the following results.1. We show that, for any integersδ, r, d with 0≤δ≤[k/2]-1,3≤r≤[k/2]+1,4≤d≤k,there are oriented complete k-partite graphs K', K", K" such that sdiam(K')-srad(K')=8, srad(K")=r, and sdiam(K'") = d.2. We determine the lower orientable strong radius and diameter of complete k-partite graphs, and give the upper orientable strong diameter and the bounds on the upper orientable strong radius of complete k-partitc graphs.We also find an error about the lower orientable strong diameter of complete bipartite graph K_m,n given in [36], and give a rigorous proof of a revised conclusion about sdiam(K_m,n).3. We show that each complete k-partite graph has an optimal strong (κ,d)-orientation.In addition, we present some problems and conjectures to be considered in future research.