## 7 Open Issues  
In this section, several challenging issues are discussed and expected to be considered in future research. \begin{table}
\begin{tabular}{c l c c c} \hline
**Ref.\({}^{1}\)** & **Problems** & \(\alpha-\textbf{Ratio}\) & **Complexity** & **Distr.\({}^{2}\)** \\ \hline
[35] & Minimize power while maintaining k-fault tolerance & \(O(k)\) & \(NA^{3}\) & Yes \\  & & \(O(k\log k)\) & & \\ \hline
[81] & Find k-connectivity sub-graph with minimum cost & \(NA\) & \(NA\) & Yes \\ \hline
[121] & Find \(k\) pairwise vertex or edge disjoint paths in an acyclic directed network with length bounded by an integer; \(L\) is the sum of all edges & \(NA\) & \(O(|V|^{k+1}L^{2k-2})\) & NO \\ \hline
[121] & Find two vertex or edge disjoint paths in a directed network, such that the maximum length of two path is minimized & at least 2 & NA & NA \\ \hline
[123] & The reliability of the two disjoint-path connection equals 1 & NA & \(O(|E|\log|V|)\) & NO \\ \hline
[76] & Assign minimized transmission power to each sensor, such that the induced topology containing only bidirectional links is strongly connected & \(k^{2}+O(k)\) & NA & NO \\ \hline
[27] & Establish k-connectivity by placing additional sensors geographically between existing pairs of sensors with a minimum number of additional sensors & 2 & \(O(|V|^{2}\log|V|)\) & NO \\ \hline
[102] & Place the minimum number of relay nodes for maintaining network connectivity, such that the transmission range of each sensor does not exceed a constant & 3, 2.5 & \(O(|V|^{3})\) & NO \\ \hline
[104] & Steiner tree problem with minimum number of Steiner points and bounded edge length (STP-MSPBEL) & 5 & NA & NO \\ \hline
[80,105] & Minimal number of relay nodes for a 2-connected network & \(O(D\log n)\) & \(O((k|V|)^{2})\)[80] & NO \\ \hline
[79] & Find the smallest 2-connectivityweighted spanning sub-graph & \(1+\varepsilon\) & NA & NO \\ \hline
[45,103] & Find the minimum count and position of relay nodes & NA & \(O(n^{4})\)[103] & NO \\ \hline
[106] & Minimum number of edges required to be added to obtain a 2-vertex or 2-edge connected plane geometric graph & NA & NA & NO \\ \hline
[28] & A minimum number of node placement for full k-connectivity and partial k-connectivity in the heterogeneous networks in terms of non-identical transmission range & \(O(\sigma k^{2})\) & NA & NO \\ \hline
[85] & Directed k-strong connectivity with a minimal overall power assignment for uniformly-spaced nodes on a line or planar space & \(min(2,\frac{\Delta}{2})^{\alpha}\) & NA & NO \\ \hline \end{tabular} \({}^{1}\) Reference; \({}^{2}\) Distributed algorithm; \({}^{3}\) Not applicable.  
\end{table} 
Table 1: NP-complete and NP-hard problems in resilient WSNs. (1) More Realistic Transmission Model for WSNs:  
The network model in many research papers is still too ideal. As shown in [38] for a TelosB testbed and [92,93] for a MicaZ testbed, the empirical studies performed show that link quality varies significantly over time, due to human activity and the multi-path effect. The work in [38] suggests that increasing transmission power up to \(-7\) dBm can improve the link quality; however, by further increasing the transmission power, the link quality actually decreases. For a specific transmission power, communication distance and antenna direction, the link quality still varies over time [92]. Those practical results imply that the realistic model of network is much more complex. The probabilistic approach can play a role here. The work in [130] provides one alternative model for an irregular communication range. The irregular radio is modeled as the degree of irregularity (DOI), which is defined as the maximum radio range variation per degree change in the direction of radio propagation. There are upper and lower bounds for radio propagation. If the neighbor node is out of the upper bound, then it is out of the communication range; while if the node is below the lower bound, it is in the communication range; if the distance is between the upper and lower bounds, the model is described as DOI.