# Multilayer Backbones for Internet of Battlefield Things +
## 3 Proposed Heuristic Distributed Algorithms  
### Distributed CDS in a Multilayer Network  
The calculation of a \(MCDS\) by any heuristic algorithm means in practice that we are seeking for \"strategically\" positioned nodes in the network topology having many connections in order to decrease the size of the obtained \(CDS\). In the case of IoBT networks, we seek for such nodes but with the additional property that they should have many interlayer links. So, the use of the _clPCI centrality_ measure [5] is a perfect fit. We exploit _clPCI_ and incorporate it into a distributed algorithm for calculating a \(CDS\); we name this distributed algorithm as the _Cross layer Connected Dominating Set_ algorithm (\(CCDS\)). \(CCDS\) is composed by the _CDS construction task_, and the _redundant relay node pruning task_. As it is common in almost any distributed algorithm for wireless ad hoc networks, each node learns the topology of its neighborhood with the exchange of beacon messages. In \(CCDS\), each node learns its 2-hop neighborhood \(N^{2}(u)\); then, it calculates its _clPCI_ and broadcasts it to its neighbours and, by mutuality of the distributed algorithm, it becomes aware of its neighbors' _clPCI_ values.  
The initial \(CDS\) construction task is a _source-initiated_ relay node selection type of algorithm, and is divided into the _neighbor prioritization subtask_ and the _construction subtask_. Each node \(u\) prioritizes (i.e., sorts) its 1-hop neighbors in decreasing order of their _clPCI_ values and _progressively_ selects from this sorted list neighbors to include in its relay set \(R(u)\) those neighbors that have the largest _clPCI_ value and that cover at least one new node in the respective 2-hop neighborhood \(N^{2}(u)\), until all \(N^{2}(u)\) is covered. Then, the _pruning task_ follows, in order to reduce (if possible) the size of its relay set \(R(u)\). \(CCDS\) uses the _restricted pruning Rule_\(k\) because it is more efficient in reducing the relay node set than several existing schemes that still ensure full broadcast coverage. Differently from this scheme, we exploit connectivity information as this is quantified by _clPCI_ in order to establish a total order among nodes that participate in the \(CDS\). \(CCDS\)'s pseudo-code is Algorithm 1.  
```
precondition:Known clPCI index values of nodes in \((N(u))\wedge(N^{2}(u))\) postcondition:Completed MCDS election process remarks:mlNetworkG=(V,E) where \(V\) and \(E\) are vertex & edge set, \(R(u)\) : relay node set of node \(u\in V\), \(M(u)\) :(T)rue/(F)alse indicator for node \(u\) being a DS node.
1 repeat
2 Add to \(R(u)\) node \(l\in N(u)\) which has the largest \(clPCI\) and covers at least one new node in \(N^{2}(u)\);
3 until each node in \(N^{2}(u)\) is covered by node(s) in \(R(u)\)
4 Announce \(R(u)\);
5 if selected as a relay nodethen
6\(M(u)=T\); Announce status change;
7 Build \(S_{(u)}^{constrained}=u_{1},u_{2},\ldots,u_{n}\mid u_{k\;(1\leq k\leq n)}\in N(u) \wedge N^{2}(u)\), \(M(u_{k\;(1\leq k\leq n)})=T\), \(clPCI(u)<clPCI(u_{k\;(1\leq k\leq n)})\);
8 if\(S_{(u)}^{constrained}\) is subject to \(N(u)\subset N(u_{1})\cup N(u_{2})\cdots\cup N(u_{n})\) and \(u_{1},u_{2},\ldots,u_{n}\) form a connected graphthen
9\(M(u)=F\); Announce status change;
10 Return; /* CDS Pruning */
11
12 end if
13
14 end for
```  
**Algorithm 1**CCDS