Nscale

Shuai Tong, Jiliang Wang, Yunhao Liu

LoRa, a representative Low-Power Wide Area Network (LPWAN) technology, has been shown as a promising platform to connect Internet of Things. Practical LoRa deployments, however, suffer from collisions, especially in dense networks and wide coverage areas expected by LoRa applications. Existing collision resolving approaches do not exploit the modulation properties of LoRa and thus cannot work well for low-SNR LoRa signals. We propose NScale to decompose concurrent transmissions by leveraging subtle inter-packet time offsets for low SNR LoRa collisions. NScale (1) translates subtle time offsets, which are vulnerable to noise, to robust frequency features, and (2) further amplifies the time offsets by non-stationary signal scaling, i.e., scaling the amplitude of a symbol differently at different positions. In practical implementation, we propose a noise resistant iterative symbol recovery method to combat symbol distortion in low SNR, and address frequency shifts incurred by CFO and packet time offsets in decoding. We propose optimized designs for diminishing the time costs of computation-intensive tasks and meeting the real-time requirements of LoRa collision resolving. We theoretically show that NScale introduces < 1.7 dB SNR loss compared with the original LoRa. We implement NScale on USRP N210 and evaluate its performance in both indoor and outdoor networks. NScale is implemented in software at the gateway and can work for COTS LoRa nodes without any modification. The evaluation results show that NScale improves the network throughput by $3.3\times $ for low SNR collided signals compared with other state-of-the-art methods.

A. Quamar, Amol Deshpande, Jimmy J. Lin

There is an increasing interest in executing complex analyses over large graphs, many of which require processing a large number of multi-hop neighborhoods or subgraphs. Examples include ego network analysis, motif counting, finding social circles, personalized recommendations, link prediction, anomaly detection, analyzing influence cascades, and others. These tasks are not well served by existing vertex-centric graph processing frameworks, where user programs are only able to directly access the state of a single vertex at a time, resulting in high communication, scheduling, and memory overheads in executing such tasks. Further, most existing graph processing frameworks ignore the challenges in extracting the relevant portions of the graph that an analysis task is interested in, and loading those onto distributed memory. This paper introduces NScale, a novel end-to-end graph processing framework that enables the distributed execution of complex subgraph-centric analytics over large-scale graphs in the cloud. NScale enables users to write programs at the level of subgraphs rather than at the level of vertices. Unlike most previous graph processing frameworks, which apply the user program to the entire graph, NScale allows users to declaratively specify subgraphs of interest. Our framework includes a novel graph extraction and packing (GEP) module that utilizes a cost-based optimizer to partition and pack the subgraphs of interest into memory on as few machines as possible. The distributed execution engine then takes over and runs the user program in parallel on those subgraphs, restricting the scope of the execution appropriately, and utilizes novel techniques to minimize memory consumption by exploiting overlaps among the subgraphs. We present a comprehensive empirical evaluation comparing against three state-of-the-art systems, namely Giraph, GraphLab, and GraphX, on several real-world datasets and a variety of analysis tasks. Our experimental results show orders-of-magnitude improvements in performance and drastic reductions in the cost of analytics compared to vertex-centric approaches.

A. Quamar, Amol Deshpande, Jimmy J. Lin

D. Lumsden

JeongHoon Min