# On Localized Countermeasure Against Reactive Jamming Attacks in Smart Grid Wireless Mesh Networks
## 5 Localized Trigger Identification Algorithm
### Trigger Nodes Detection Procedure
#### 5.2.2 Identification of a Single Trigger Node (ISTN) Algorithm  
The _ISTN_ algorithm in Algorithm 3 illustrates the localized process to identify a trigger device with maximum 'index' among an ordered set \(U\). It divides sequentially the group into two halves, similar to the binary search manner. However, the algorithm always performs the group testing to detect the presence of the wireless trigger devices in the right half first so that the one with the maximum index (the rightmost) would be returned, when there are triggers among \(U\). The _ISTN_ algorithm finalizes the process whenever a trigger device is located. In a clear sense, the identification of a trigger among a group \(U\) from the Smart Grid wireless devices from the algorithm _ISTN_ requires at most \(\log_{2}(|U|)\) testing rounds. ```
1 ISTN Function (\(U\)) Input :\(U=\{v_{1},v_{2},\ldots,v_{m}\}\) Output :\(v_{k}\) s.t \(k=\max\{i\mid v_{i}\text{ is a trigger}\}\) or output no triggers. 2 whilelow \(<\)highdo\(mid=\lfloor\frac{1}{2}(low+high)\rfloor\)\(T=\{v_{mid},\ldots,v_{high}\}\) /* Entire devices of a group \(N_{\text{it}}\) conduct the following procedure to identify triggers*/ Devices within \(U\) broadcast the message of \(TEST_{1}\) in the time slot of \(t_{\text{test}}\)
3 ifNo Detection on \(JammingSignal\) at \(t_{\text{test}}+\frac{r}{s}\)laterthen
4 if\((low=high)\)then
5 Return \(v_{low}\) and exit;
6 else
7\(low=mid\);
8
9 end if
10 else
11\(high=mid-1\)
12
13 end if
14
15 end for return No Triggers
16
17 end while
18 return No Triggers
19
20 end while
21 return No Triggers
22
23 end while
24
25 end while
26 return No Triggers
27



Figure 4: Trigger Nodes in a Hexagon. ## 6 Theoretical Performance Analysis

### Upper Bound on Testing Rounds

**Lemma 5**: _Trigger identification ends as soon as all triggers in the convex hull \(C_{T}\) are identified._

All other triggers are also detected following _Quick Identification_. One more round of group testing for all the remain nodes will show there are no more triggers among them. **Theorem 1**: _Algorithm 2 requires no more than \(O(|C_{T}|\log\Delta)\) number of rounds where \(|C_{T}|\) is the number of vertices on the convex hull of the set of triggers._

The key observation is that in every round of the while loop, the chosen \(v_{t}\) by ISTN will have the maximum distance to the arbitrary convex hull of the identified triggers (since the nodes in \(U\) are sorted based on the distance to that convex hull). That point must belong to the convex hull \(C_{T}\). Hence, the algorithm loops for at most \(|C_{T}|\) times and requires at most \(O(|C_{T}|\log\Delta)\) round. Since we can perform testing for all hexagons of same color at the same time, the total number of rounds to identify all triggers in the network will be \(c\times(\max\{c_{t}\}\log\Delta+1)\) where \(c\) is the number of colors in Lemma 4 and \(\max\{c_{t}\}\) is the maximum size of convex hull of a group of triggers in a hexagon. Although \(\max\{c_{t}\}\) may go up to \(\Delta\), the algorithm's performance is often far better than its worst case. ### Message Complexity

**Lemma 6**: _In Algorithm 2, the number of messages sent by nodes inside a hexagon \(H\) is \(O(n_{H}+n_{H}\times t_{H})\) where \(n_{H},t_{H}\) are the number of nodes, triggers inside \(H\) respectively._

In the first phase of Algorithm 2 checking for the existence of triggers requires all nodes within the hexagon transmit at once. Hence, it costs \(n_{H}\) messages. In the second phase, identifying one trigger node among \(n_{H}\) nodes using \(ISTN\) algorithm will cost \(n_{H}/2+n_{H}/4+\ldots+1=n_{H}\) messages. The number of message in the second phase is, hence, at most \(O(n_{H}\times t_{H})\). Adding the numbers of messages in two phases we get \(O(n_{H}+n_{H}\times t_{H})\). Adding the number of messages in all possible hexagons we get the following theorem.