## 4 Optimization Mechanism Design
### General Design of DDAR
#### Phase 1:
3:For each \(\mathcal{S}_{\sigma}\) received by the senisng node do
4:If\(l(Q_{\varepsilon})==\mathcal{S}_{\sigma}\)then
5:\(Dest(\varepsilon)\)=\(\sigma\)
6:Return
7:Endif
8:Endfor
9:If there is no aggregator whose \(\mathcal{S}_{\sigma}\) is equal to \(l(Q_{\varepsilon})\)
10:\(\operatorname{index}=l(Q_{\varepsilon})-1\)
11:while\(\operatorname{index}>0\)do
12:For each \(\mathcal{S}_{\sigma}\)do
13:If\(S_{\sigma}==\operatorname{index}\)then
14:\(Dest(\varepsilon)=\sigma\)
15:Return
16:Endif
17:Endfor
18:index-
19:Endwhile
20:\(\operatorname{index}=l(Q_{\varepsilon})+1\)
21:While\(\operatorname{index}\leq\mathcal{Q}\)do
22:For each \(\mathcal{S}_{\sigma}\)do
23:If\(\mathcal{S}_{\sigma}==\operatorname{index}\)then
24:\(Dest(\varepsilon)=\sigma\)
25:Return
26:Endif
27:Endfor
28:\(\operatorname{index}++\)
29:Endwhile
30:Endif
```  
**Algorithm 2** Establishment of Routing for a Sensor \(\varepsilon\). Figure 7: The sample operations in phase 3. The explicative remarks about Algorithm 2 are shown below:  
Lines 3-8: Sensor searches an aggregator whose service tag is equal to the level of the sensor's service requirements. Lines 11-19: If there is no aggregator owning the corresponding service tag, the sensor searches an aggregator which has a better service from bad to good. Lines 20-29: If there is no aggregator with no corresponding service or better, the sensor starts to find an aggregator with a worse service from good to bad. The complexity analysis is described below:  
The number of the aggregators in the network is set as \(N\). the time that sensor broadcasts and receives message is \(O(1)\). Then the sensor selects an aggregator with the corresponding tag. The overhead of this step is \(O(N)\). If there is no such an aggregator, the sensor would go through the tags twice at most. Therefore, the time complexity of a sensor selects an aggregator is as Equation (7):  
\[O(1)+O(N)+O(N)+O(N)=O(N) \tag{7}\]  
_Phase 4:_ Finding the next hop of data packet queue  
While sensors choose their data transmission aggregators, aggregators issue service tag queries to the surrounding aggregators in the upper layer (closer to the sink) to determine the next hop route. The candidate aggregators with no tag are informed to set the tag when there is no aggregator has the same tag. Then that node set \(N_{t}\) and \(T_{t}\) using Equation (6). If there is still no aggregator with the same tag, the aggregator would from bad to good select an aggregator with a better service. If there is no aggregator with a better service, the aggregator selects a node with a worse service from good to bad. If the sink is in the predetermined range, the aggregator selects the sink as next hop. As shown in Figure 8, the tag of \(\alpha\) is 1, in its neighbor aggregators, \(\gamma\)'s tag is same as \(\alpha\). \(\alpha\) chooses \(\gamma\) as its next hop. Same reasoning, \(\beta\) regards \(\delta\) as its next hop. Figure 8: The sample operations in phase 4. The details can be described as the following algorithm. The explicative remarks about Algorithm 3 are shown below:  
Lines 3-8: Aggregator searches an aggregator whose service tag is equal to the aggregator's service tag. Lines 9-13: The aggregator finds a neighbor aggregator with no service tag as its next hop and gives the tag to that aggregator. Lines 15-24: If there is no aggregator owning the corresponding service tag or no tag, the aggregator searches an aggregator which has a better service from bad to good. Lines 25-34: If there is no aggregator with no corresponding service or better or no tag, the aggregator starts to find an aggregator with a worse service from good to bad. ```
1: Aggregator \(\sigma^{i}\) sends a broadcast message to aggregators in its predetermined communication range to inquire the tag of service of each node. 2: Each aggregator replies a message to inform the tag of service \(\mathcal{S}_{\sigma^{i-1}}\) to the sensor.