# Distributed Reliable and Efficient Transmission Task Assignment for WSNs
## 5 Reliable and Efficient Task Allocation Algorithm for WSNs
### Distributed Task Assignment
#### 5.2.2 Distributed Reliable and Efficient Task Allocation in Planar Topology
During this process, if the current time of the system exceeds the task deadline, the task allocation is interrupted. When the network update occurs, if the scope of the update involves only one sink (represented by \(sink_{k}\)), then \(sink_{k}\) multicasts the update request to other sinks. According to the NWR model, the number of copies that need to be written to the update is \(W-1\). \(W\) in this paper should satisfy \(W>N-2\). If the number of sinks in response to the update request is higher than \(W-1\), \(sink_{k}\) submits the view update, and other sinks in the multicast group update the local-global view accordingly. Otherwise, the update of \(sink_{k}\) is deleted to avoid inconsistency with other different sink views. When the sink finds that the task transmission is lower than the reliability threshold, the task allocation is re-executed. The specific process of Algorithm 2, TRETA-Multi-Sink is as follows:```
1 Input: \(TG_{j}(V,E)\), \(RT_{j}(S,Ps)\), \(M(t)\), \(R_{s}\), \(C_{i}\)
2 Output: \(\varphi(m_{i}):M\to V\), \(\phi(m_{i}):L\to E\)
3\(TG(V,E)=\text{Merge}(TG_{j}(V,E))\), \(j=1,2,\ldots n\)
4\(RT(V,E)=\text{Merge}(RT_{j}(V,E))\), \(j=1,2,\ldots n\)
5 for\(\forall m_{i}\), \(m_{i}\in M(t)\)
6 get \(T\), \(S_{i}=T\)
7 if\(S_{i}<C_{i}\)
8\(sink_{j}=\big{\{}sink\big{|}\text{Mindistinct}(m_{i},sink),sink\in TG_{j}(V,E) \big{\}}\)
9 read \(sink_{j}\),\(viewID\) and \(sink_{j}\),\(viewID\)
10 if\(sink_{j}\),\(viewID\
eq sink_{j}\),\(viewID\)
11 read view of \(\text{latest}\big{(}sink_{j}\),\(viewID,sink_{j}\).\(viewID\big{)}\)
12 else read \(sink_{j}\),\(RT_{j}(S,Ps)\)
13 call TRETA \((TG_{j}(V,E),RT_{j}(S,Ps),M(t),\ R_{s})\)
14 get \(T\)
15 if\(T>C_{i}\), return line 1
16 if\(TG(V,E)\) change happens and \(Num(\text{changed}\ \ \sin\text{k})=1\)
17\(sink_{k}\) record change in cache
18\(sink_{k}\) multicast update-request to other sinks
19 if\(Num\big{(}sink_{k}^{res}\big{)}>W-1\)
20\(sink_{k}\) submit an update
21 update\((sink_{k}.TG_{j}(V,E)\), \(sink_{k}.RT_{j}(S,Ps),sink_{k}.log\big{)}\)
22 update\(\big{(}sink_{k}^{res}.TG_{j}(V,E)\), \(sink_{k}^{res}.RT_{j}(S,Ps),sink_{k}^{res}.log\big{)}\)
23 else delete \(sink_{k}\)record
24 if\(R_{WSN}<R_{s}\), then
25 return line 3
26 return
```

**Algorithm 2**TRETA -Multi-sink

## 6 Performance Analysis

### Theoretical Analysis

In this section, the performance of distributed reliable and efficient task allocation is analyzed primarily from the algorithm complexity, communication load, and delay of the task assignment. #### 6.1.1 Algorithm Complexity

TRETA-Cluster is divided into two phases. In the first phase, the sink performs task allocation for the backbone network composed of the cluster heads and the sink, with the worst-case calculation complexity \(O(\left(\alpha N\right)^{3})\), where \(\alpha\) represents the ratio of the size of the backbone network to the size of the entire network system. During the second phase, the cluster head is responsible for the task allocation within the cluster. The calculation complexity of this process is \(O(\left(\gamma N\right)^{3})\), where \(\gamma\) represents the ratio of the cluster member nodes size to the entire network size. Based on the above process, the calculation complexity of distributed task allocation based on clustering topology is \(O\left(N^{3}\right)\). In TRETA-Multi-Sink, the calculation complexity of multiple sinks in local task allocation is the same as TRETA, although the processing of global view consistency is added to the network update in TRETA-Multi-Sink, which includes the write operation of multiple sinks when global view update occurs and read operation when task assignment occurs. Assuming \(N\) is the network size, \(\beta\) is the ratio of the part of the network to be updated, and \(W\) is the number of global views that need to be written, the calculation complexity of the write operation is \(O(\beta\text{WN})\). Let the number of global views that need to be read is \(R\) (\(R=2\)); then, the calculation complexity of the read operation is \(O(2N)\).