# A New Lightweight Watchdog-Based Algorithm for Detecting Sybil Nodes in Mobile WSNs
## 4 Proposed Algorithm  
The following entities are the core to the proposed algorithm. * \(\mathbf{A_{co-prs}^{k}}\)**:** This is an upper-triangle \(H\times H\) matrix which contains the co-presence status of all node pairs at time index \(k\). The elements of \(A_{co-prs}^{k}\) are in the form of \(xy:x,y=0/1\) where 0 and 1 represent absence and presence respectively (Figure 2a). In Figure 2, \(H\) refers to the total number of Sybil and normal-node IDs which is equal to: \[H=N+M*S\] (1) where \(N=|SN|\), \(M=|MN|\), and \(S\) equals the number of Sybil IDs per malicious node. * \(\mathbf{C_{co-prs}^{k}}\)**:** This matrix which is structurally similar to \(A_{co-prs}^{k}\) (upper-triangle \(H\times H\)) scores the co-presence of each node pair at time index \(k\) (Figure 2b) and is updated according to \(A_{co-prs}^{k-1}\), \(A_{co-prs}^{k}\) and the co-presence state diagram model. * \(\mathbf{Co-presence}\)** state diagram model**:** This diagram shows how a transition between co-presence states of ID pairs updates the elements of the \(\mathbf{C_{co-prs}^{k}}\) matrix (Figure 3). The algorithm is described in steps, with numbered references to the flowchart of Figure 4, as follows. * **Initialization phase Step I 1**: Each WD constitutes of matrices \(A^{k}_{co-prs}\) and \(C^{k}_{co-prs}\) and fills the former with 00s corresponding to the general co-absence status. * **Information collection phase Step II 2**[3][4]: Hello Packets are broadcasted by normal and malicious nodes at fixed time intervals (movement steps). Following each movement, all WD nodes update their neighbors lists by overhearing these Hello Packets. Step III 5**: Each WD forms the new \(A^{k}_{co-prs}\) based on its current neighbors list as follows. Two-digit binary numbers 00, 11, and 10/01 correspond to co-absence, co-presence, and  
Figure 4: Flowchart of the proposed algorithm. Figure 3: Co-presence state diagram model of ID pairs. alternate-presence statuses respectively. Specifically, if \(1D_{i}\)_and_\(1D_{j}\
otin neighbors-list\), the content of element (\(ID_{i}\), \(1D_{j}\)) of matrix \(A^{k}_{co-prs}\) is set to 00. On the other hand, if \(1D_{i}\)_and_\(1D_{j}\in neighbors-list\), this content is set to 11. Finally, if \(1D_{i}\in neighbors-list\) and \(1D_{j}\
otin neighbors-list\) (or vice versa), the content of the corresponding element of \(A^{k}_{co-prs}\) is set to 10. These values also represent the states in the co-presence state diagram model. **Step IV 6):** By comparing the contents of the corresponding elements of \(A^{k-1}_{co-prs}\) and \(A^{k}_{co-prs}\), the content of the corresponding element of \(C^{k}_{co-prs}\) is updated according to the transitions in the state diagram. For instance, when \(A^{k-1}_{co-prs}[ID_{i},ID_{j}]=00\) and \(A^{k}_{co-prs}[ID_{i},ID_{j}]=11\), according to the state diagram, \(C^{k}_{co-prs}[ID_{i},ID_{j}]\) must be increased. **Step V 7 [8]:** In this step, \(A^{k}_{co-prs}\) is updated so that the elements of \(A^{k-1}_{co-prs}\) which are equal to 01/10 replace the corresponding elements of \(A^{k}_{co-prs}\) (trap states are preserved). Steps II to V are repeated for a predetermined number of times representing the network's lifetime. **Detection phase Step VI 9 [9] [10] [11] [12]:** All WDs send their co-presence information \(C^{k}_{co-prs}\) (labeled as \(C^{k}_{co-prs-z}\)) to a designated WD node. The designated WD then checks the elements of \(C^{k}_{co-prs-z}\) for each WD and creates a \(C_{co-prs-final}\) matrix according to:  
\[C_{co-prs-final}[ID_{i},ID_{j}]=\frac{E.Func}{W} \tag{2}\]  
wherein  
\[Func=\sum_{z=1}^{W}C^{k}_{co-prs-z}[ID_{i},ID_{j}] \tag{3}\]  
and  
\[E=\left\{\begin{array}{ll}0&\mbox{if }\exists z\
eq y\ \mid C^{k}_{co-prs-y}[ ID_{i},ID_{j}],\\ &\qquad\qquad\qquad\* Information collection phase: Figure 5 shows the information collection phase of the algorithm illustrating how it proceeds step-by-step as is implemented in \(W_{1}\). The same procedure is repeated in \(W_{2}-W_{4}\) not shown here for the sake of brevity.