Connected Big Data Measurement

Rossi Kamal, Choong Seon HongarXiv 2015 · arXiv

Abstract

Managing large-scale data networks requires efficient structures to handle communication without overwhelming system resources. This paper introduces a resilient scheme for Big Data monetization that optimizes the trade-off between the size of a Connected Dominating Set (CDS) and routing efficiency. By implementing a "Resilient Path" strategy, the proposed method achieves shorter routing paths and smaller virtual backbones compared to existing state-of-the-art algorithms, providing a scalable solution for modern network environments.

Introduction

In the era of Big Data, managing every individual node in a massive network is computationally expensive and energy-inefficient. To streamline operations, researchers utilize a Connected Dominating Set (CDS), which acts as a virtual backbone. Every node in the network is either part of this set or adjacent to a node within it.

The primary challenge in CDS design is a fundamental tension between size and efficiency. A smaller CDS reduces management overhead and energy consumption but often forces data to take circuitous, high-latency routing paths. Conversely, a larger CDS improves routing speed but increases maintenance costs. This research seeks the "Goldilocks zone"—a resilient backbone that minimizes both CDS size and routing path lengths.

Methodology

The authors evaluated their proposed scheme using Unit Disk Graphs (UDGs), which simulate wireless environments where nodes connect if they fall within a specific transmission range. The core innovation is the Resilient Path strategy, which enforces a constraint where the distance between two nodes in the CDS ($d_D$) is no more than five times the shortest path in the original graph ($d_D(a, b) \leq 5d(a, b)$).

This strategy was benchmarked against several established methods:

  • Guaranteed Path: A more relaxed constraint ($7d$).
  • $\alpha$-MOC-path: A path where intermediate nodes are a multiple ($\alpha$) of the original shortest path.
  • ABPL (Average Routing Path Length): A focus on minimizing average distance.
  • Diameter-based: A focus on minimizing the maximum distance across the set.

Experiments were conducted on synthetic datasets with nodes randomly placed in a coordinate space. The transmission range varied from 10 to 40, and the network size scaled up to 100 nodes. Results were averaged over 20 randomly generated graph instances to ensure statistical consistency.

Results and Performance Analysis

The experimental results highlight the "performance supremacy" of the resilient scheme across two critical metrics: backbone size and routing latency.

CDS Size and Scalability

As shown in Figure 1, the resilient scheme consistently maintains a smaller CDS size than competing methods like alpha-moc, abpl, and guaranteed pathing as the number of nodes increases. This efficiency is particularly pronounced in denser networks. The authors observed that as network density increases, the resilient scheme leverages the abundance of intermediate nodes to find efficient paths without ballooning the backbone size.

Comparison of CDS size across different algorithms as the number of nodes increases.

Routing Efficiency

Beyond reducing overhead, the resilient scheme excels in routing performance. Figure 2 illustrates the Maximum Routing Path Length (MRPL) across different node counts. The resilient strategy (marked by stars) consistently yields the lowest MRPL, ensuring that data travels through the virtual backbone with minimal delay. This suggests that the scheme is better suited for time-sensitive Big Data applications than traditional diameter-based or guaranteed path methods.

Maximum Routing Path Length (MRPL) vs. Number of Nodes.

Discussion and Insights

A key insight from the study is the "Density Advantage." In dense environments, the resilient scheme performs better because it can identify "domination-reluctant" nodes—nodes that are well-connected but do not necessarily need to be part of the backbone to maintain connectivity. This allows the CDS size to decrease relative to the total number of nodes as the network scales, improving overall system longevity.

While the resilient scheme may require a slightly larger CDS than the most aggressive minimization algorithms at extremely high scales, the authors argue this is an acceptable trade-off for the significant gains in routing efficiency and reduced latency.

Conclusion

This paper demonstrates that a resilient approach to CDS construction can effectively balance the competing needs of backbone size and routing speed. While the current study relies on synthetic Unit Disk Graphs, which assume uniform transmission ranges, the results provide a strong theoretical foundation for optimizing IoT and sensor networks. Future work will involve testing these strategies in real-world environments with physical obstacles and exploring the direct financial benefits of these efficiencies in Big Data monetization contexts.

Summary updated

BibTeX
@misc{kamal2015connected,
  author = {Rossi Kamal and Choong Seon Hong},
  title = {{Connected Big Data Measurement}},
  year = {2015},
  eprint = {1510.04132},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1510.04132},
}
Figure