An Asynchronous Distributed Algorithm for Minimum sxe2x88x92t Cut Detection in Wireless Multihop Networks Abstract   Stable communication is a vital and challenging requirement in wireless multihop networks because nodes failure may disconnect other active nodes. Minimum st cuts can help to measure the reliability of a network regarding the nodes or links failure. A minimum st cut is the smallest subset of links that their failure disconnects all communication paths between nodes s and t. Minimum st cuts can also reveal the bottlenecks, bridges, and clusters in the network. This paper proposes an asynchronous distributed algorithm for finding minimum st cuts in wireless multihop networks. The proposed algorithm iteratively finds linkdisjoint paths from s to t and changes the direction of the selected edges to ignore them in the next iteration. After finding all paths, the undiscovered nodes in the last search determine the minimum st cut. The comprehensive simulation results on different networks with up to 500 nodes show that the proposed algorithm finds minimum st cuts in reasonable time with up to 64% and 39% lower energy consumption than the existing central and distributed algorithms, respectively.

Distributed robust timeefficient broadcasting algorithms for multichannel wireless multihop networks with channel disruption Abstract   Broadcasting is a fundamental problem for wireless multihop networks such as wireless ad hoc and sensor networks. In this paper, we study distributed robust timeefficient global broadcasting for SINRbased (i.e., SignaltoInterferenceplusNoiseRatiobased) multichannel wireless multihop networks subject to channel disruption. In this study, we make the following assumptions: i) for successful packet reception, the SINR at receivers must exceed a certain threshold; ii) an adversary exists in the network, which uniformly and randomly chooses t u003e 0 channels to disrupt from total    F    u003e 1 available channels in every round. To address the broadcasting issue in such networks, we first propose a degreeaware broadcasting algorithm and then propose a degreeindependent broadcasting algorithm. The proposed algorithms elaborately integrate distributed channel selection and transmission scheduling at different nodes while considering the following factors: the impact of SINR constraint, availability of channels, sending probability on selected channel, presence of adversary, with and without node degree information. We present the detailed design of the two algorithms. We deduce their worstcase time performance to accomplish the task of global broadcasting with high probability. We further prove that both algorithms can still preserve the same time performance under more powerful oblivious adversary and weakly adaptive adversary. Simulation results show that the proposed algorithms have satisfactory averagecase time performance.