# Design and Analysis of Adaptive Hierarchical Low-Power Long-Range Networks
## 2 A Hierarchical Communication Scheme
### Self-Organizing Sub-Network Formation  
Each device operates by dividing time into epochs of fixed duration \(T\). The length of the epochs is defined by the administrator of the network during the initial deployment of the device and can be changed dynamically during the execution of the network. The epoch of a single device is completely independent of others and there is no actual synchronization resulting in a network operation like the one presented in Figure 4 where epochs of different devices in gray and white color. When a new epoch starts for a given device, the device declares itself as a controller. This decision is signaled to all neighboring nodes by including a special bit within the beacon of the network monitoring mechanism. All devices inspect this bit and generate a list with all nearby devices that have declared themselves as controllers. This list is included in the beacons periodically broadcasted by the network monitoring mechanism. In this way, devices are informed about controllers further away up to a maximum distance of \(d\) hops. If a controller is notified about the existence of another controller, within \(d-\mathit{hops}\) distance, with a smaller unique identity (i.e., with a smaller identity provided by the MAC address of the network interface), it decides to step down accepting that the other device will be the active controller. Therefore, multiple controllers eventually step down after a period of at most \(d-\mathit{hops}\). As it is evident, the parameter \(d\) is used to control the size of the sub-networks. The parameter is initially set by the network administrator during the deployment and can be modified during the execution of the system based on a special downstream control message distributed to all the devices via the LPWAN. Essentially, the network adjusts its operation to form sub-network structures so that each device is never more than \(d\) hops away from its selected controller and at most \(2\times d\) hops away from any other member of the same sub-network. Note that, although a device may be \(2\times d\) hops away from each other in the formed sub-network, the actual distance may be smaller since each hop need not be at a maximum tranmission range. If at some point a device realizes that the previous controller is no longer available, e.g., due to a nearby nominated controller being eliminated by a final controller in a distance of more than \(d-\mathit{hops}\), or due to the duty-cycling mechanism, or due to a failure in the network, or because the controller has changed location, it restarts the process forming its own sub-network. The above mechanism guarantees that controllers are rotated periodically so that no single device keeps the role of the gateway for a long duration of time, thus overspending the available energy resources. In some cases, there can be periods where multiple devices re-initiate the controller selection mechanism resulting in increased congestion in the short-range network. As it will become evident in Section 5, this issue does not have serious impacts on the overall performance of the network. As soon as a device becomes a controller, it enters a waiting period of duration \(O(d)\) time to allow for the controller selection mechanism to stabilize. At the end of this period, the device will either be identified as the controller or not. If no other controller within distance less than \(d\) exists with a smaller unique identifier, the device is the active controller and initiates the sub-network construction phase. If another controller is located with a smaller unique identifier, then the device steps down, exits the waiting period and becomes a sub-network follower. After this waiting period, all controllers that remain active activate the sub-network formation phase by using a simple breadth-first search protocol to invite its nearby devices in its sub-network.