# 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
Based on the above process, the calculation complexity of the distributed task allocation algorithm is \(O(N^{3})\). The two distributed task allocation algorithms above reduce the size of the network. As noted, the distributed task allocation has the polynomial computation complexity in the background of global optimization. #### 6.1.2 Communication Load of the Distributed Task Assigned

In the distributed task allocation strategy for the clustered topology, the sink multicasts the allocation policy to the selected cluster heads that are responsible for the task allocation within the cluster. Therefore, the communication load depends on the amount of information in the sink's allocation policy. In this paper, the communication load of TRETA-Cluster is measured by the number of packets in the allocation policy by multicast, as shown in Equation (15):

\[CM=Num_{cp} \tag{15}\]

For the multi-sink topology, the communication load includes: (1) multi-casting the global view between the sinks, namely \(Num_{gc}\), where \(Num_{gc}\) represents the communication load for transmitting one global view, and \(a\) represents the number of times of global views transmitted; (2) ensuring global view consistency between multiple sinks, i.e., the write load \(WM\) at update time and the communication load \(RW\) at read time, as shown in Equation (16):

\[DM=\mathrm{a}Num_{gc}+WM+RW \tag{16}\]

where only the version and update operation of the global view is transferred when the update is written, and performed only when the network is updated, as shown in Equation (17):

\[WM=\left\{ \begin{array}{c}V\mathit{UIM}\\ 0\end{array} \right. \tag{17}\]

where \(V\mathit{UIM}\) indicates the write load of the version and update operation of the global view when it is updated, and 0 means no update. When the sink reads the global view, it needs to read two copies of the global view; that is, the global view of the local and that of the nearest sink in the network, as required by the final consistency. If the local version of the global view is newer, there is no need to communicate with other sinks, and thus the communication load of the read is 0. Otherwise, one global view needs to be transmitted. Therefore, the communication load \(RW\) when reading is as shown in Equation (18):

\[RM=\left\{ \begin{array}{c}0\\ Num_{gc}\end{array} \right. \tag{18}\]

#### 6.1.3 Delay of Distributed Task Assignment

In order to implement the task assignment, two known premises are required: the physical topology of the entire network and the routing topology of the network established in advance. They are considered in the initialization process for the task assignment, so the delay is not considered at initialization. The task assignment delay for a clustered topology is calculated by Equation (19):

\[RT_{d,c}=RT^{\prime}_{c}+MC+CHD \tag{19}\]

where \(RT_{d,c}\) represents the delay of task assignment for the clustered topology, \(RT^{\prime}_{c}\) represents the delay of the sink allocating a task to the subgraph composed of the cluster heads, \(MC\) represents the delay of the multicast performed by the sink, and _CHD_ represents the delay in the allocation of the task by the selected cluster head. Assuming that each sink has obtained a global view in a multi-sink deployment environment, this stage can be implemented by periodically swapping local views with each other through multiple sinks, requiring it as initialization prior to the task assignment. The delay for distributed task allocation based on multiple sinks is calculated by Equation (20):

\[RT_{d\_d}=\overline{RT_{c}^{\prime}}+\mathrm{C}_{rt}. \tag{20}\]

where \(RT_{d\_d}\) represents the delay of TRETA-Multi-Sink, \(\overline{RT_{c}^{\prime}}\) represents the average of the delays of the tasks assigned by multiple sinks locally, and \(\mathrm{C}_{rt}\) indicates the time to ensure the final consistency of the view, as shown in Equation (21):

\[\mathrm{C}_{rt}=\left\{ \begin{array}{l}\mathrm{W}_{rt}\\ \mathrm{R}_{rt}\end{array} \right.