Security and routing issues in wireless networks.
详细信息
文摘
Wireless networks have been widely used in industries, military and education. We usually represent a wireless network as a Unit Disk Graph (UDG) G ＝ (V, E). There are many issues considered in wireless networks. In this dissertation, I mainly focused on the security and routing issues which are two of the most important issues in wireless networks. Security is one of the important issues in wireless networks. Secure clustering problem plays an important role in distributed sensor networks. Weakly Connected Dominating Set (WCDS) is used for solving this problem. Therefore, computing a minimum WCDS becomes an important topic of this research. I compared the size of Maximal Independent Set (MIS) and minimum WCDS in unit disk graph. The analysis showed that five is the least upper bound for this ratio. I also presented a distributed algorithm to produce a weakly connected MIS within a factor 5 from the minimum WCDS. DENIAL-OF-SERVICE (DoS) attack, which aims to make a service unavailable to legitimate clients, is another threat to the internet security. I made a connection between group testing and internet security. Group testing is a technique to detect the defective items with minimum number of tests. It tests the items by group instead of one by one to save the testing times. I used group testing technique to test which server or application is being attacked. Group testing is a technique to detect the defective items with minimum number of tests. It tests the items by group instead of one by one to save the testing times. Routing is another most important issues in wireless networks. A good routing path can save much energy. Energy consumption is always a big concern in wireless networks. Connected Dominating Set (CDS) is a popular way to construct the virtual backbone in wireless network. I showed that a minimum nonsubmodular cover problem could be reduced into a problem of minimum submodular cover with submodular cost. And I approached to the solution of MOC-CDS problem by showing a little weaker result using Generalized Hitting Set.