# Distributed Reliable and Efficient Transmission Task Assignment for WSNs
## 5 Reliable and Efficient Task Allocation Algorithm for WSNs
### Distributed Task Assignment
#### 5.2.1 Distributed Reliable and Efficient Task Allocation in a Hierarchical Topology
```
Input: \(\mathbf{TG}(V,E)\), \(\mathbf{RT}(S,Ps)\), \(M(t)\), \(R_{s}\), \(\mathbf{C}_{i}\) Output: \(\varphi(\mathbf{m}_{i}):M\to V\), \(\phi(\mathbf{m}_{i}):L\to E\)
```  
```
1 for\(\forall m_{i}\), \(m_{i}\in M(t)\)
2 get\(T\), \(S_{i}=T\)
3 if\(S_{i}<C_{i}\)
4 for\(\forall C\)\(H\), \(CH\in RT(S,Ps)\) //\(CH\) represents the cluster head
5\(R_{CH}=RA(RT(S,Ps))\)
6\(R_{CM}=RA(RT(S,Ps))\)
7 for\(\forall C\)\(H\in RT_{b}(S,Ps)\)
8 call TRETA \((TG_{b}(S,Ps),RT_{b}(S,Ps),R_{CH})\)
9 for\(\forall\) Cluster \(\in RT(S,Ps)\)
10 call TRETA \((TG_{c}(S,Ps),RT_{c}(S,Ps),R_{CM})\)
11 if call TRETA \((TG_{c}(S,Ps),RT_{c}(S,Ps),R_{CM})\
eq\varnothing\)
12 return allocation result
13 get \(T\)
14 if\(T>C_{i}\), return line 1
15 if\(CH\) fault
16 sink update \(TG(V,E)\) and \(RT(S,Ps)\)
17 if\(R_{WSN}<R_{s}\), then
18 call TRETA \((TG_{\mathcal{P}}(V,E),RT_{\mathcal{P}}(S,Ps),R_{CH})\)
19 elseif the failed cluster is re-clustered
20 sink update \(TG(V,E)\) and \(RT(S,Ps)\)
21 if member of \(CH\) change
22 sink update \(TG(V,E)\) and \(RT(S,Ps)\)
23 if\(R_{WSN}\geq R_{s}\), then return
24 else
25 call TRETA \((TG_{\mathcal{P}^{\prime}}(V,E),RT_{\mathcal{P}^{\prime}}(S,Ps),R_{CM})\)
26 if call TRETA \((TG_{\mathcal{C}}(V,E),RT_{\mathcal{P}^{\prime}}(S,Ps),R_{CM})\
eq\varnothing\)
27 return allocation result
28 else return line 1
29
30 if\(R_{WSN}<R_{s}\), then
31 return line 1
32 return
```  
**Algorithm 1**TRETA-Cluster  
It can be noted that the local task allocation of the cluster head may select the node participating in the task, and since the path from the cluster head to the sink has been obtained in the first stage, the selection from the node to the path is completed in two phases in a task assignment. Whenever the nodes in the cluster change (join or leave), the cluster head transmits the topology change to the sink. The sink determines whether the node change affects the reliability of the task. If not, it returns. Otherwise, the cluster head node tries to re-select the node in the cluster after the change. Additionally, if the intra-cluster target reliability constraint can be met, the cluster head re-performs the local task assignment. Otherwise, the sink performs the task allocation again. When the sink finds that the task transmission is below the reliability threshold, the task allocation is performed again. However, when the cluster head fails, the cluster will disconnect from other parts of the network and the task assignment policy issued by the sink cannot reach the cluster, bringing challenges to the reliable task allocation of WSNs. The proposed processing scheme follows: the sink updates the two-level global view and determines whether the fault of the cluster has an impact on the target reliability of the current task. If so, the task is reassigned according to the updated two-level global view. Otherwise, the sink only updates the two-level global view that reduces the frequency of the update. After the faulty cluster re-selects the cluster head, the cluster head collects the cluster topology and the sink node updates the global view and reperforms the task assignment.