Applications Of Graph Theory In Computer And Wireless Sensor Networks

The invention of computer is a landmark of computing history, it completely improves the traditional computing technique. It can provide more powerful computing capacity, making computing more rapid, accurate, and have the ability to store results. Modern computer as the most advanced and popular computing technique plays an important role in human's daily life and scientific effort. It gives the evolution of other techniques even sciences a great push forward.This dissertation uses graph theory as modeling tool to investigate the relative hot problems on the most popular modern computer architectures, including parallel computer architecture, wireless sensor networks, and grid computing architecture.This dissertation includes five chapters, divide into three subjects. The first is fault-tolerant adaptive routing in mesh networks, including two important modern parallel computer architecture 2D mesh and n-D mesh. The second subject is the routing protocol for tracking a mobile target in wireless sensor networks. I developed An Efficient grid scheme for mathematical computing, called Mathematics Internet Computing Environment (MICE for short) in my third subject. I study the first two subjects mainly in UniversitéParis-Sud 11, France (July, 2007 - June, 2009) and the last two subjects in Lanzhou University, China (September, 2005 - June, 2007).Specifically, I will give a brief introduction about the backgrounds and the state of arts of the modern computer architectures and especially of the issues that I concerned in Chapter 1. Chapter 2 an Chapter 3 will be the contents of the fault-tolerant adaptive routing problems in 2D mesh and n-D mesh respectively. I present the routing algorithms for tracking a mobile target in wireless sensor networks in Chapter 4, including the comparison with the traditional algorithm. The detail information of MICE is proposed in Chapter 5.In Chapter 2 and 3,I focus on faulty-tolerant adaptive routing in mesh networks. A novel faulty block model is proposed, which is cracky rectangular block, for fault-tolerant adaptive routing. Based on this model, all the faulty nodes and faulty links are surrounded in several blocks, which are a convex structure, in order to avoid routing livelock situation. My contribution is that constructs the interior spanning forest for each block in order to keep in touch with the nodes inside of each block. The procedure for block construction is dynamical and distributed. It is ease of implementation and executed locally by each node of the networks. And this is a fully adaptive block which will dynamically adjust its scale in accordance with the situation of networks, either the fault emergence or the fault recovery, without shutdown and reboot the system as others did. Based on this model I also provide a distributed fault-tolerant routing algorithm. A proof is given to guarantee messages always reach their destinations if and only if the destination nodes keep connecting with this mesh networks especially for the nodes including in blocks. The new model and routing algorithm maximize the availability of the nodes in networks. This is a noticeable overall improvement of fault-tolerability of the system.In Chapter 4, I focus on the routing algorithm of tracking a mobile target in wireless sensor networks. Along with the advancement in wireless communications and electronics, I first propose a novel application problem in WSNs. It is the Data forwarding of real-time mobile target tracking problem. We mainly focus on the researches of the strategy of routing the tracking data to several sinks with the consideration both of energy conservation and latency limitation. I propose three different heuristic methods (Minimum Latency Routing, Maximum Utilization Routing and Active First Routing respectively) to research and compare their performance for solving the problems. I also use the traditional Dijkstra's shortest path algorithm to get the lower bound of the latency limitation. As a result, I found that the active first routing (AFR) algorithm is better than others, it achieves the similar latency limitation with Dijkstra's and it get a 1.2-1.5 times of energy conservation than other algorithms regardless of energy supplement conditions. It is a optimal algorithm for this problem.In Chapter 5, A Grid Computing model in math is designed based on current network computing technologies. MICE is an emerging technology to provide uniform programming, task submission, and management specifications across the large scale distributed computing nodes which deployed some famous mathematical software. MICE utilizes a three-level architecture that shields users from low-level computing resource discovery and provides globe uniform view for users. We extended MathML to solve the mathematical semantic objects' expression. CSP (Computing Service Platform) servers are adopted in MICE to provide uniform task access, transfer and management of heterogeneous distributed resources across multiple administrative domains. This architecture enables the mathematical software resources to be deployed as services on the internet. MICE can achieve good scalability, reliability and can be flexibly deployed and configured.