# Resource Indexing and Querying in Large Connected Environments
## 5 Proposed Approach
### Index Generation Algorithm  
As mentioned before, the global index generation algorithm will be only summarized here. More details can be seen in [2]. We will, however, use a different illustrative use case (a set of devices having different capacities). We note that a global index generation  
Figure 4: Algorithm steps example with 4 devices, 4 covered (Z1–Z4) and 2 uncovered zones (Z5–Z6). Figure 3: Global & Local Device indexes in a sub-environment. algorithm could be used in many cases (such as for all devices) but we use it in our case for the cluster heads only (following our architecture). To generate the global index, we use two main algorithms: (1) preprocessing of the global index using Algorithm 1, and (2) add indexes using Algorithm 2 to create a device to zone relation. ```
Input :Set of Cluster head Devices \(D\), set of Capacities \(C\), Covered Zones \(Z\) Output :global // Initial global index matrix \(||D||\), \(||Z||+||Z||||\); // index creation with # rows=D and # cols=zones \(Sort(global,\mathit{Asc},C)\); // index ascending ordering according to capacities Return global
```  
**Algorithm 1**PreProcessingGlobalMatrix()  
``` Input :\(z\);\(g\);\(a\),\(g\) Output :\(g\);\(\mathit{Local}\) Variables:\(\mathit{start\_row}=0,\mathit{cpt}=1,\mathit{max\_capacity}\) for(\(\mathit{i\in\mathit{m}}\),\(\mathit{[g\_l]}\)) {if(\(\mathit{i



reflects the total number of zones, encompassing both covered(left side of the index) and uncovered (right side of the index) (line 1). If the cluster head device's capacity is the minimum (i.e., 2 in our study), then it has a local index with an entry containing its zone and another entry with the address of a super node (e.g., gateway). If the capacity \(d.c\) is sufficient to index all zones (d.c \(\geq||Z||+||\bar{Z}||\)), the device will contain information about all zones. If the capacity is between the minimum defined and \(||Z||+||\bar{Z}||\), then Algorithm 2 is applied to generate the final global index. Algorithm 2 takes the initialized global index from Algorithm 1, \(\alpha\) which is the number of entries in the covered zone part of the matrix (defined by the user ) and \(\beta\) which is the number of entries in the uncovered zone part of the matrix (defined by the user). In our approach, \(\alpha\) must always be greater than \(\beta\) to favor covered zones over uncovered zones. In our running example, \(\alpha\) equals 3, and \(\beta\) equals 1, the four devices (\(d1,d2,d3\), and \(d4\)) have capacities equal to 1, 2, 3, and 4, respectively (after omitting the entry of the related super nodes for each one of them). We start by obtaining the starting row in the index, to reduce the execution time of the algorithm, since devices that have already maximized their capacity do not need any further processing (lines 1-4). In lines 5-9, we assign each cluster head device to its zone by detecting its maximum coverage within the environment. This step can be seen in Figure 4 (Step 1). \(\alpha\) is decremented by one at the end of this step. In lines 10-12, we create a minimal cycle between devices for covered zones. The importance of this step is to initiate communication between all the covered zones. The next device entry, when capacity allows, is chosen following a specific distribution strategy to assign the next covered cell (random, biggest capacity, closed, etc.). In our case, we will add an index for the device \(D_{i+1}\). Each device will index the zone next to it in the matrix, except the devices whose zones are in the last column. In this case, they add an index for the first zone, since we need to loop between all the covered zones. Step 2 in Figure 4 shows the minimal cycle generation. \(d2\) adds an index for \(z3\) since \(d2\) is located in \(z2\) and the location \(z3\) is next to the zone \(z2\) in the index. For \(d4\) an index is added for \(z1\), since \(z5\) is an uncovered zone. \(d1\) does not add an index, since it has a capacity of 1.