
## 3 Frogsim: An Algorithm For Distributed Graph Coloring

Although the FrogSim algorithm will be described in terms of **an algorithm applied in static**
sensor networks, it can be applied with very few modifications in any other communication network. The algorithm works iteratively using communication rounds. A communication round corresponds to the calling period (2π**) as known from the models presented in the** previous section. The only difference is that the length of a communication round is considered to be one time unit. Therefore, the numerical length of a communication round is denoted by 1, instead of 2π**. Each sensor node executes exactly one sensor event in each communication** round. The moment in time when a sensor node i ∈ V **executes its sensor event is denoted by**
θi ∈ [0, 1). Note that θi **corresponds to the phase of an oscillator from the models presented**
in the previous section. Apart from θi, a sensor node i **also stores its current color, denoted**
by ci ∈ N**. For simplicity and without loss of generality, we assume that each color is uniquely**
identified by a natural number. Thereafter we will use natural numbers greater than zero to refer to colors. Moreover, a sensor event includes the sending of exactly one message.

Therefore, each sensor node i maintains a message queue Mi**for sensor event messages received**
from other sensor nodes since the last execution of its own sensor event. The pseudo-code of a sensor event is shown in Algorithm 1. In the following we give a rough description of the algorithm. Detailed technical explanations of the functions of Algorithm 1 will be provided later on.

Before the algorithm can be started, it is actually necessary to determine a virtual treeshaped topology over the sensor network. This task is achieved by using any method from the literature to generate a minimum spanning tree **in a distributed manner (see, for example, [16, 3, 17, 12]). This tree will determine a single root node that will become a distinguished node of the network (also called the master) with some additional functionalities in**
comparison to the rest of the nodes. Once this tree has been created, the master node runs a protocol to measure the number of hops (that is, communication rounds) necessary to reach the farthest node in the network. Note that this measure corresponds to the height of the Algorithm 1 **Sensor event of node** i 1: if less than K communication rounds executed **then**
2: θi:= **recalculateTheta**()
3: ci:= **minimumColorNotUsed**()
4: **sendColoringMessage()**
5: αi:= αi/ρ 6: **else**
7: if first communication round of Phase II **then**
8: if (ci = 1) then pi:= **randomPositiveInteger**()
9: else pi:= 0 **endif**
10: else if ∃m ∈ Mi| (powerm ≥ pi) **then**
11: ci:= **minimumColorNotUsedByNeighborsWithHigherPower()**
12: pi:= **adoptPowerFromStrongestNode()**
13: **end if**
14: **sendRefinementMessage()** 15: **end if**
16: **clearMessageQueue()**