ABSTRACT This study investigates the dynamic Steiner tree problem. The objective of the Steiner tree problem is to compute a minimum‐weight tree connecting a set of designated vertices called terminals in a connected weighted graph with positive real edge weights. A dynamic graph is one in which the set of edges, the set of vertices, or both can change over time. Here, we focus on dynamic graphs where edges can change over time. The work begins by establishing a lower bound on the update time required to maintain an MST heuristic based ‐approximate Steiner tree (where is a small fraction) in a general graph undergoing edge insertions or deletions. Subsequently, we propose two dynamic algorithms: A fully dynamic algorithm to maintain an approximate Steiner tree in planar graphs and an incremental algorithm to maintain an approximate Steiner tree in general graphs. We focus on edge‐weighted connected graphs. The graph undergoes dynamic updates where edges with specific weights can be either inserted or deleted. The goal is to efficiently compute a Steiner tree of the updated graph, guaranteeing a solution quality (Steiner tree cost) within a good factor of the optimal Steiner tree. In the fully dynamic case, our analysis demonstrates that the presented algorithm maintains an approximation factor of . The worst case update time for processing a series of number of updates is where is the cardinality of the vertex set of the input graph, denotes the unweighted diameter of the updated graph, and . It is shown that the update time can be improved to in a special case. On the other hand, the incremental algorithm maintains an approximate Steiner tree in general graphs with an approximation factor of under edge insertions. It achieves an update time of . Here is the shortest path diameter of the modified graph. The fully dynamic algorithm leverages concepts from an existing Steiner tree algorithm and a dynamic distance oracle. On the other hand, the incremental algorithm maintains a partition of the input graph in the form of a shortest path forest, which aids in efficiently updating a Steiner tree.

ABSTRACT Given two distinct sets of items and a set of agents, each with combined preferences for selecting one item from each set, the question arises: How can we optimally assign pairs of items to agents? To address this, we investigate the popular matching problem in a 3‐uniform 3‐partite hypergraph. In this setting, the first partition represents agents, while the second and third partitions represent two different types of items. Agents express preferences over the hyperedges incident to them, whereas the items have no preferences. A matching is called popular if there exists no matching that a majority of agents prefer over . Since determining the existence of a popular matching is NP‐hard in a 3‐uniform 3‐partite hypergraph, we focus on approximating such matchings using the concept of unpopularity factor . The unpopularity factor is defined as the maximum ratio over all other matchings , where and are the sets of agents preferring the matching and , respectively. We first present an exact algorithm that computes a popular matching in exponential time if it exists, or it notifies the nonexistence of such a matching. To address efficiency, we design an approximation algorithm that constructs a matching in a 3‐uniform 3‐partite hypergraph with unpopularity factor , where is the maximum degree of any agent. Additionally, we show that , where is the number of agents, implying . The approximation algorithm runs in time, where is the number of hyperedges.

For real-time edge computing applications working under stringent deadlines, communication delay between IoT devices and edge devices needs to be minimized. Since the generalized assignment problem being NP-Hard, an optimal assignment of IoT devices to the edge cluster is hard. We propose the application RL based heuristics to obtain a near-optimal assignment of IoT devices to the edge cluster while ensuring that none of the edge devices are overloaded. We demonstrate that our algorithm outperforms the state-of-the-art.

High processing capabilities of today's large systems are also used for real time applications, where executing tasks before their deadline is essential. On the other hand, with increase in the processing capability, energy consumption also increases for such systems. Thus energy efficient execution of real time tasks in such large systems has found to be promising research area in recent time. Scheduling tasks in such large systems using only low level power construct like DVFS is not efficient. In this paper, we have exploited the power consumption pattern of the recent commercial processors and derived a simple power model with a higher granularity for systems have large number of processor with each processor having multi-threading feature. We have then proposed an energy efficient scheduling technique namely, smart allocation policy for executing a set of aperiodic independent real time tasks on large system such that no task misses it deadline. We have analyzed the instantaneous power consumption and the overall energy consumption of the proposed policy along with other five baseline policies for a wide variety of synthetic data sets and real trace data. As execution time of tasks has a significant impact on scheduling and on the overall performance of the system, we have considered six different execution time models of task for our experiment. Experimental evaluation reveals that our proposed policy performs significantly better than baseline policies for all the variations of synthetic data and for real trace data.

Abstract Signature‐based intrusion detection systems (IDSs) are employed to monitor computer networks for signs of network intrusions. However, they produce a large number of false positive alarms when operated with default settings without considering the underlying network environment. Inundation of false alarms is the Achilles heel of IDS technology, which could render the IDS ineffective in detecting network attacks. Several false alarm minimization approaches have been proposed in the literature. However, there are many drawbacks associated with these works, namely, modification of well‐established attack signatures; heavy dependence on the attack signatures' reference numbers, which might not always be available; and non‐consideration of the underlying network context information. In this paper, we propose an efficient game theory‐based false alarm minimization scheme for signature‐based IDS. The proposed scheme uses a game theory‐based correlation engine to correlate IDS alarms with network vulnerabilities to minimize the overall false positive alarm rate of the IDS. Experimental results and comparison analysis of the proposed false alarm minimization framework with other frameworks on the benchmark DARPA intrusion detection evaluation dataset and an in‐house IIT Guwahati Lab dataset show that the proposed scheme achieves the highest accuracy among all the frameworks under consideration without degrading the overall detection rate of the IDS. Copyright © 2016 John Wiley & Sons, Ltd.

Consider a distributed system with n processors, which receive triggers from the outside world. The distributed trigger counting (DTC) problem is to raise an alarm if the total number of triggers over the system reaches w, which is an user-specified input. DTC is used as a primitive operation in many applications, such as distributed monitoring, global snapshots, etc. Many of the earlier studies on DTC was done using non-deterministic algorithms. In this paper, we propose a deterministic algorithm for the DTC problem with a message complexity of O(n log w log n) and each node in the system receives O(n log w) number of messages, which is an improvement over earlier result for certain values of w. The distribution of triggers among the n nodes may be arbitrary. This paper gives insight into the deterministic algorithm for the DTC problem. Also to the best of our knowledge the overall message complexity and per node message complexity are better than earlier deterministic algorithms.

Wireless sensor networks have grown significant attentions among researchers for providing a flexible and low-cost framework to design an architecture for Intelligent Transport Systems. The inherent challenges in distribution and management of sensor networks along the road require an application-specific protocol support for the network connectivity, the sensing coverage, the reliable data forwarding, and the network lifetime improvement. This paper introduces the concept of k-strip length coverage along the road, which ensures a better sensing coverage for the detection of moving vehicles compared with the conventional barrier coverage and full area coverage, in terms of the availability of sufficient information for statistical processing and the number of sensors required to be active. To extend the network lifetime, every sensor follows a sleep-wakeup schedule maintaining the network connectivity and the k-strip length coverage. This scheduling problem is modeled as a graph optimization, the NP-hardness of which motivates to design a centralized heuristic, providing an approximate solution. As a sensor network is inherently distributed in nature, properties of the centralized heuristic are explored to design a per-node solution based on local information. Performance of the proposed scheme is analyzed through simulation results.

Data gathering or converge cast is one of the most popular applications of road side sensor network where the data sensed from the road are accumulated in the road side gateways or sinks for traffic monitoring purpose. The required delay sensitivity and reliability of the application as well as the scarcity of sensor resources make the task challenging. In this paper, a novel tree based data gathering scheme has been proposed exploiting the strip like structure of the road network. Sensor nodes are distributed in several virtual blocks along the road and a converge cast tree is constructed selecting one active node from each block. Implementation of efficient scheduling assures both the coverage and critical power savings of sensor nodes. The network connectivity is guaranteed throughout by the proposed tree maintenance module that handles the sensor node joining and leaving events. Simulation results show that the tree maintenance overhead in terms of both delay and control message communication is nominal.

Sensor networks deployed for the border area monitoring requires a high degree of reliability for the data gathering in spite of any arbitrary node or sink failures. This paper proposes RelBAS, a robust data gathering scheme specially designed for the border area network to provide a guaranteed delivery of sensory data. The proposed protocol aims to find out multiple node-disjoint paths to multiple sinks so that the disconnectivity in one path due to a node failure does not disrupt the delivery of data to the sink. The forwarding path selection at every node in RelBAS is based on the combination of three parameters - the hop-count, the residual energy and the number of children for for parent of the corresponding tree. This helps in adapting the protocol to the application requirement depending on the delay, energy efficiency and data aggregation. Moreover, RelBAS is capable of detecting an affected zone due to multiple node failures. The effectiveness of the proposed scheme has been analyzed using the simulation results.

The lifetime of sensor network depends on the efficient utilization of resource-constrained sensor nodes. Several MAC protocols like DMAC and its variants have been proposed to save critical sensor resources through sleep-wakeup scheduling over data gathering tree. For applications where data aggregation is not possible, the sleep duration decreases gradually from the leaves to the root of the data gathering tree. This results early failure of sensor nodes near the sink, and affects network connectivity and coverage. Deploying redundant sensors can solve this problem where a faulty node is replaced by a redundant node to maintain network connectivity and coverage. However, the amount of redundancy depends on the node failure pattern, and thus more number of redundant nodes required to be deployed near the sink. This paper proposes a gradient based sensor deployment scheme for energy-efficient data gathering exploring the trade-off among connectivity, coverage, fault-tolerance and redundancy. The density of deployment is estimated based on the distance of a node from the sink while dealing with connectivity, coverage and fault-tolerance. The effectiveness of the proposed scheme has been analyzed both theoretically and with the help of simulation.

Event driven data gathering or convergecast through sensor nodes requires efficient and correct delivery of data at the sink. A tree rooted at the sink is an ideal topology for data gathering which utilizes sensor resources properly. Resource constrained sensor nodes are highly prone to sudden crash. A set of algorithms, proposed in this paper, builds a data gathering tree rooted at the sink. The tree eventually becomes a Breadth First Search (BFS) tree where each node maintains the shortest distance in hop-count to the root to reduce the routing delay and power consumption. The data gathering tree is repaired locally within a constant round of message transmissions after any random node fails. Simulation result shows that the repairing delay is very less in average, and the proposed scheme can repair from arbitrary node failure using constant number of message passing.