On several graph related algorithms and protocols in wireless security
This dissertation studies graph-theoretic problems related to security protocols in wireless networks. Many current wireless protocols lack necessary security and reliability measure due to the properties of wireless networks. In many cases, we can model a wireless network as a graph, and many security problems are related to problems in graph theory. In our research, we mainly focus on the following issues: (1) Minimum cost blocking in wireless mesh networks. In wireless mesh networks, outgoing data traffic usually goes out from a node inside the network to a number of gateways. The advantage of sending traffic to different gateways is that it can improve both reliability and security. Especially for some threshold security protocols, for a specific node, if the number of correctly received data packets heading for different destinations are more than a certain threshold, then the protocols can be executed correctly. If an adversary can block a certain number of paths related to a node, then the number of correctly received data packets originating from the node may be smaller than the threshold, and the adversary achieves his/her goal. We demonstrate the general version of minimum cost blocking problem, show its hardness and designed several approximation algorithms for it. (2) Report dropping and tampering detection in sensor networks. Achieving communication dependability in sensor networks is difficult due to limitations on node power and wireless channel unreliability. We use a new measure of node disjointedness to find proxy route to improve security and reliability, we also show that to find an optimal proxy route is NP-hard, and give a detailed analysis of the proxy route based schemes. (3) Time difference related problems. Time difference related problems originate from group time synchronization protocols in wireless sensor networks. In these protocols, every group member needs to synchronize their clock since there will be some time difference after they are deployed. In many cases, the group time synchronization protocol is executed in a cluster where a node can compute the time difference between itself and its neighboring nodes. We introduce the Maximum Consistent Time Difference (MCTD) subgraph problem and the Minimum Time Difference Adjustment (MTDA) problem, analyze their hardness, and propose some algorithms for MCTD. (4) Key update protocol related problems. We generalize the ideas and principles of the hierarchical key structure, and analyze several graph related problems in key update protocols.