# Implementation of a Topology Independent MAC (TiMAC) Policy on a Low-Cost IoT System
## 3 The TiMAC Policy  
TiMAC is a TDMA-based policy, the latter policies dividing the time into slots and each node is able to access the channel at a given time slot. Note that, in TDMA, all nodes share the same frequency channel; thus, they have to be synchronized for ensuring that interference will not be experienced during transmissions. In this sense, under TiMAC, a fixed-length frame is assigned to all nodes, while the time-slot duration is considered to be long enough for a transmission of a data packet to take place. The next step is to assign to each node a subset of the previously assigned frame's time-slots, during which a node is allowed to transmit its data packet. The latter time-slot assignment takes place according to arbitrarily assigned Galois polynomials [30] as described next. The goal here is to ensure a unique subset for all nodes--thus further ensuring that each node will transmit according to a unique repeating pattern. As a result, at least one transmission will be successful for each node during every frame, even if the network load is increased (e.g., each node always has data packets available for transmission) [17]. As already mentioned, under the TiMAC policy, nodes are assigned time-slots according to arbitrarily assigned Galois polynomials, the latter procedure being derived by the Chlamtac-Farago algorithm [17]. In order for the TiMAC policy to exploit the Chlamtac-Farago algorithm and operate, certain assumptions have to be made regarding the total number of nodes composing the network, as well as the maximum number of neighbors each node can have. Let \(N\) denote the number of network nodes and \(D\) the maximum number of neighbors, respectively. \(N\) and \(D\) are used by the algorithm in order to derive the values of two new (integer) parameters, the first related to the size of the frame and denoted by \(q\), and the second related to the degree of Galois polynomials of order \(q\) and denoted by \(k\). More specifically, the frame size consists of \(q^{2}\) time-slots (i.e., the frame size is \(q^{2}\)), each one split into \(q\) sub-frames of \(q\) time-slots. Each node is assigned one slot from each one of the \(q\) sub-frames and, therefore, each node is allowed to transmit at \(q\) time-slots within a frame. Having made the above assumptions, the next step is to derive the particular time-slots during which it is allowed for a certain node \(u\) to transmit its data packet. For deriving the latter time-slot,each node \(u\) is assigned a unique polynomial of degree \(k\) with coefficients from a finite Galois field of order \(q\) (\(GF(q)\)), to be represented as  
\[f_{u}(x)=\sum_{i=0}^{k}a_{i}x^{i}\]  
where \(a_{i}\in\{0,1,2,\ldots,q-1\}\). In order to find the slot assigned to each node \(u\) inside a subframe \(s\), \(f_{u}(s)\bmod q\) is calculated, where \(s\in\{0,1,\ldots,q-1\}\)[17]. It is reasonable to suppose that, in order to achieve the constraint for unique polynomials assigned to all nodes in the network, it is required that \(q^{k+1}\geq N\) (\(q^{k+1}\) corresponds to all possible polynomials of degree \(k\) when their coefficient belong to the \(GF(q)\)). An integral property of this approach is that, in each frame, at least one transmission will be successful for each node even for the case of increased traffic load conditions. For example, even if all nodes always have data packets ready to be transmitted, each node will have at least one collision-free slot during the frame. Taking into account that each node transmits according to its assigned polynomial of degree \(k\), there will be at most \(k\) simultaneous transmissions (thus collisions will occur) with any neighbor node since there are at most \(k\) common roots between two polynomials of degree \(k\). Considering that the maximum number of neighbor nodes is \(D\), then at most \(kD\) simultaneous transmissions are expected to take place. In addition, given that each node is allowed to transmit at \(q\) time-slots, then \(q\geq kD+1\) so as to guarantee at least one successful transmission.