# Routing in Mobile Wireless Sensor Networks: A Leader-Based Approach+
## 3 A Leader-Based Routing Approach (LBR)
### Building the Communication Tree
#### 3.2.1 Protocol LBR1  
Our first implementation relies on delivering the routing information as soon as possible in a reactive way. In this regard, a node \(p_{i}\) computes the \(sinkBy_{i}\) election during a whole round. When a message with a higher round number is received by a node \(p_{i}\), \(p_{i}\) broadcasts a leader message with the result of the previous round computation and the increase of the distance received (The distance is extracted from contextual information stored in the message.) (see Lines 5-11, of Algorithm 1). Thus, \(p_{i}\) sends its own leader message using the last distance to \(s\) known by \(p_{i}\). Observe in Algorithm 2 that no other node but \(s\) will send in its leader message a zero distance value. These new leader messages sent by \(p_{i}\) is essential for multi-hop scenarios. First, leader messages propagate the existence of a sink node in the system. Second, the periodic broadcast of the leader message allows for other nodes to become connected. Finally, leader messages provide the required information to its neighbourhood to create the spanning tree. Consequently, the reception of a new round identifier from \(s\) by a node \(p_{i}\) enables a new election round in every \(p_{i}\), which eventually results in a reconfiguration of the spanning tree. Figure 1: Example sequence illustrating how a spanning tree is built by our algorithms. Solid lines represent spanning tree arcs. (**a**) the sink node \(s\) starts executing the protocol; (**b**) the spanning tree is built from \(s\); (**c**) the spanning tree is complete. Observe that it has been reconfigured in the meanwhile; (**d**) a new node, \(p_{5}\), joins the network; (**e**) a new reconfiguration due to mobility; and (**f**) node \(p_{2}\) disconnects from \(p_{1}\) and becomes not connected. ```
1 Initially:timeout \(\leftarrow\)\(v\)\(\{v>\beta\}\);
2 call(reset());
3
4\(||\)Task 1:a:when\((j,\textsc{leader},\textit{sender},\textit{round},\textit{distance})\) is received at time \(t\) such that \(j\in N_{i}(t)\) and \(W_{i\leftarrow j}(t)\geq\{(tech)\}\) {When receiving a leader message}
5 ifround \(>\)\(current\)\(Round_{i}\)then
6\( broadcast(\{\textsc{leader},i,current\)\(Round_{i},sink\)\(Distance_{i}+1\})\);
7\(sinkBy_{i}\gets next\)\(SinkBy_{i}\);
8\(next\)\(SinkBy_{i}\gets sender\);
9\(sink\)\(Distance_{i}\gets distance\);
10\(current\)\(Round_{i}\gets round\);
11\(\textit{set timer\_connectivity}\); to timeout;
12
13 elseifround \(=\)\(current\)\(Round_{i}\)then
14 if\(sink\)\(Distance_{i}=distance\)and\(\textit{sender}>sinkBy_{i}\)then
15\(next\)\(SinkBy_{i}\gets sender\);
16
17 elseif\(sink\)\(Distance_{i}>distance\)then
18\(next\)\(SinkBy_{i}\gets sender\);
19\(sink\)\(Distance_{i}\gets distance\);
20
21 end if
22
23 end if
24 ifnot\(connected_{i}\)then
25\(connected_{i}\leftarrow\)True;
26\(sinkBy_{i}\gets next\)\(SinkBy_{i}\);
27
28 end if
29
30 end if
31
321 end if
332
341 end if
353
362 end if
373
38 end if
390
391 end for
```  
**Algorithm 1**The algorithm LBR1 executed by any sensing node \(p_{i}\). Lines 26-38 are also shared with LBR2. ```
1\(round1d\gets 0\);
2\(||\)Task 1:each\(\beta\) time
3\(round1d\gets round1d+1\);
4\(broadcast(\{\textsc{leader},s,round1d,0\})\);
5
6 end if
70
81 end for
```  
**Algorithm 2**Algorithm executed by the sink node \(s\). The fact that the sink node broadcasts leader messages periodically (Algorithm 2) allows for a timer-based monitoring of connectivity changes. The first time that a node \(p_{i}\) receives a leader message (let us say, at time \(t\)) from any \(p_{j}\in N_{p_{i}}(t)\), \(p_{i}\) becomes connected and will remain connected during the time interval \((t,t+timeout]\) (The \(timeout\) variable has a common value slightly higher than \(\beta\) in order to prevent premature time outs.) by setting the timer \(timer\_connectivity_{i}\) by Line 11. In this way, every \(p_{i}\in N_{i}(t)\) will become connected by Lines 21-24 and will change their variable \(sinkBy_{i}\) pointing to \(s\) (Lines 7 and 8).