## 4 Description of the Proposed Topology Construction
### Chain Construction Algorithm for the Proposed Topology  
The proposed chain construction algorithm consists of three steps, namely (i) generating the shortest-path chain; (ii) link exchange; and (iii) pruning. Step one generates an initial single chain, which is derived using the Kruskal minimum spanning tree algorithm. This initial chain may not be optimised, because of the existence of some cross links. At steps two and three, these cross links are removed, and the chain is reconstructed and pruned to multiple chains. The chain construction algorithm is depicted in Figure 7, and detailed descriptions of each step are provided below.  
**Step 1**  
\(A=\{\) 1, 2, 3,..., \(N\}\) // set of sensor nodes  
\(SH=\phi\) // set of links \(L(i,j)\)  
Assign \(C[i][j]=C_{ij}\)  
for.(\(\forall i\in A\)) node[\(i\)].peer_leaf = \(i\)  
repeat until \(A\) contains two elements  
\(i\)/ there would be two leaf nodes in the initial chain  
Find \(i\) and \(j\) that minimize \(C[i][j]\)  
such that (\((i,j\in A)\)\(\&(i\
eq j)\)\(\&(\)node[\(i\)].peer_leaf \(\
eq j)\))  
construct_chain(\(i,j\))  
**Procedure construct_chain(\(i,j\))**  
place (\(i,j\)) in \(SH\)  
node[\(i\)].peer_leaf].peer_leaf= node[\(j\)].peer_leaf  
node[\(j\)].peer_leaf].peer_leaf= node[\(i\)].peer_leaf  
if (node[\(i\)].peer_leaf \(\
eq i\)) remove \(i\) from \(A\)  
if (node[\(j\)].peer_leaf \(\
eq i\)) remove \(i\) from \(A\)  
_// SH_ contains all the links that constitute the initial chain  
**Step 2**  
do  
Start tracing the chain starting from any leaf node.  
Find crossed links (\(w,x\)) and (\(y,z\))  
if (\(C(x,y)+C(w,z)\leq C(w,x)\)+\(C(y,z)\))  
\(SH=SH-(w,x)\), (\(y,z\))  
\(SH=SH+(x,y)\), (\(w,z\))  
until all nodes are traced  
**Step 3**  
Divide the chain constructed after step 2 into multiple chains with  
similar number of nodes in each chain  
**Step 4**  
Figure 7: Chain construction algorithm.  
_Step 1. Configuring the initial chain._ This step generates an initial chain, which is derived from the Kruskal minimum spanning tree algorithm by giving an additional constraint of a maximum degree of 2. This algorithm selects a link, one by one, through a specified routine. Since links are selected as long as a loop does not occur, several complex chains (see Figure 3(b)) can be generated during the chain generation. When some links are formed, the next link is the shortest link among links that connect those nodes whose degree is under 2. However, the two end nodes are not included in the same sub-chain.  
_Step 2. Link Exchange._ For large number of nodes, there is a high possibility that the initial chain generated after step 1 includes some cross links (see Figure 8). In this step, cross links are removed, and the chain is pruned to multiple chains. The cross link removal process takes place when there are available links whose lengths are shorter than that of the cross links. This process is called link exchange.  
In Figure 8, the nodes are numbered from 1 to \(n\). In this figure, dotted lines represent sub-chains that are consisted of several links. The solid lines in this figure represent a single link. When the process of link exchange occurs, the order of sub-chain from \(i+1\) to \(j\) is reversed. To exchange two links of the chain as from \((i,i+1)\) and \((j,j+1)\) to \((i,j)\) and \((i+1,j+1)\), the following condition should be satisfied: \(C(i,i+1)+C(j,j+1)\geq C(i,j)+C(i+1,j+1)\) where \(C(i,j)\) denotes the length of the link \((i,j)\).  
_Step 3. Pruning._ At the end of the link exchange, an optimal chain is generated. To create multiple chains from this optimal chain, each node of this chain is traced, starting from the farthermost end of the chain from the BS. The tracing process takes place from one node to its neighbouring node until the number of nodes traced is equal to \(C_{N}\). Here, \(C_{N}\) is the optimal number of node in a chain. At this point all nodes that have already been traced are pruned from the initial chain. This pruning process continues until all the nodes of the initial chain are traced.