## 3 The PPBR Key Management Scheme
### Path Key Establishment  
PPBR scheme establishes the communication link based on a certain probability, thus there are some nodes which may not be able to communicate with the MS node, and this will reduce the network connectivity. It must establish an indirect communication link in the path key establishment phase when the MS and sensor nodes cannot establish a session key directly. The path key establishment method used in this article is different from the conventional polynomial key management scheme, and it utilizes the tree-based construction method in wireless sensor networks [35]. It builds a tree which regards the sink node as a root within the scope of the sink node's communication. The schematic diagram is shown as Figure 4.  
Suppose that the _status_ and the _depth_ denote whether the nodes are in the range of sink node's communication and the depth of the tree, respectively. The initial values of _status_ and _depth_ are all 0. The steps of the process can be summarized as follows:  
First, MS broadcasts request information to sensor nodes within the scope of communication, the information contains MS identifier, _ID_ table (_ID_ identifiers of \(M\) polynomials) of the polynomial ring, and _ID_ table (_ID_ identifiers of \(m\) keys) of the key ring: MS \(\rightarrow^{*}\): Req(_ID\({}_{\text{MS}}\)list_(ID\({}_{\text{PK}}\))\({}_{\text{M}}\),list_(_ID\({}_{\text{Ki}}\))\({}_{\text{m}}\),depth = 1_).  
Second, sensor node \(S_{i}\) within the range of communication will set the value of _status_ as 1, and then match the _list_(ID\({}_{\text{PK}}\)) and _list_(_ID\({}_{\text{Ki}}\)) received from the MS with the polynomials and keys stored inside the sensor node. If there are shared polynomials and the keys, the sensor node \(S_{i}\) makes the value of _depth_ add 1. Then, the sensor node \(S_{i}\) will send response packets to the MS, the information contains: sensor nodes _ID_, mobile node _ID_, the shared polynomial _ID_ table (_ID_ identifiers of \(S\) polynomials, \(1\leqslant S\leqslant N\)), and the shared key _ID_ table (_ID_ identifiers of _S'_ keys, \(1\leqslant S^{\prime}\leqslant n\)): \(S_{i}\to MS\): Res\(\{\)ID\({}_{i}\)ID\({}_{\text{MS}}\),list_(ID\({}_{\text{PK}}\))\({}_{\text{S}}\),list_(_ID\({}_{\text{Ki}}\))\({}_{\text{S'}}\}\).  
If there are no shared polynomials and the shared keys, the sensor node \(S_{i}\) will discard the broadcast packets from the MS.  
Finally, sensor node \(S_{i}\) broadcasts request information to its neighbor nodes again, the information includes: MS identifier _ID\({}_{\text{MS}}\)_, _ID_ table (_ID_ identifiers of \(N\) polynomials) of the polynomial ring, and _ID_ table (_ID_ identifiers of \(n\) keys) of the key ring which are all pre-stored in the sensor node: \(S_{i}\rightarrow^{*}\): Req(_ID\({}_{\text{MS}}\),list_(ID\({}_{\text{PK}}\))\({}_{\text{N}}\),list_(_ID\({}_{\text{Ki}}\))\({}_{n}\),depth = 2_).  
In the scope of the node's communication, the sensor node \(S_{i}\) will make the value of _depth_ add 1, and send the response information at the same time once finding out the shared polynomials and keys.  
With the above steps, sensor nodes within the range of communication can be joined into the tree as much as possible, so that sensor nodes are able to increase connectivity by establishing a multi-hop communication link to the sink node. The session key between target node MS and source node \(S_{i}\) can be obtained by the indirect session key \(K_{\text{IMi}}\) established by the intermediate nodes: \(K_{\text{MS}-Si}=hash(K_{\text{IM1}}\ |\ K_{\text{IM2}}\ \ldots\ |\ |\ K_{\text{IMi}})\).  
Figure 4: Path key establishment method via the tree-based construction.