With the growth of the Internet of Things (IoT), the number of cyber attacks on the Internet is on the rise. However, the resource-constrained nature of IoT devices and their networks makes many classical security systems ineffective or inapplicable. We introduce TWINKLE, a two-mode, adaptive security framework that allows an IoT network to be in regular mode for most of the time, which incurs a low resource consumption rate, and to switch to vigilant mode only when suspicious behavior is detected, which potentially incurs a higher overhead. Compared to the early version of this work, this article presents a more comprehensive design and architecture of TWINKLE, describes challenges and details in implementing TWINKLE, and reports evaluations of TWINKLE based on real-world IoT testbeds with more metrics. We show the efficacy of TWINKLE in two case studies where we examine two existing intrusion detection and prevention systems and transform both into new, improved systems using TWINKLE. Our evaluations show that TWINKLE is not only effective at securing resource-constrained IoT networks, but can also successfully detect and prevent attacks with a significantly lower overhead and detection latency than existing solutions.

A Cybersecurity Operations Center (CSOC) performs various tasks to protect an organization from cyber threats. Several types of personnel collaborate to function effectively as a team to analyze the threat signals, in the form of alerts, arriving from various sources. Teams are often formed ad hoc, resulting in an imbalance in their performances and thereby increasing the risk associated with the low-performing teams. The current approach taken by behavioral scientists in forming effective teams focuses on first qualitatively assessing individuals such as analysts, who are then grouped into teams based on their credentials and expertise. Our work takes a holistic view of the CSOC by first defining team requirements and then selecting individuals to form several collaborative teams that meet these requirements for every shift of operation. We present a novel team formation framework that integrates optimization, simulation, and scoring methods to form effective teams and introduce a new collaborative score metric that measures their effectiveness. Results from simulated experiments show the formation of effective teams whose collaborative scores are maximized and balanced. Our approach is also able to identify high and low performers within the first few months of implementing the framework.

The deployment of monoculture software stacks can have devastating consequences because a single attack can compromise all of the vulnerable computers in cyberspace. This one-vulnerability-affects-all phenomenon will continue until after software stacks are diversified, which is well recognized by the research community. However, existing studies mainly focused on investigating the effectiveness of software diversity at the building-block level (e.g., whether two independent implementations indeed exhibit independent vulnerabilities); the effectiveness of enforcing network-wide software diversity is little understood, despite its importance in possibly helping justify investment in software diversification. As a first step towards ultimately tackling this problem, we propose a systematic framework for modeling and quantifying the cybersecurity effectiveness of network diversity, including a suite of cybersecurity metrics. We also present an agent-based simulation to empirically demonstrate the usefulness of the framework. We draw a number of insights, including the surprising result that proactive diversity is effective under very special circumstances, but reactive-adaptive diversity is much more effective in most cases.

Cyber-security is an important societal concern. Cyber-attacks have increased in numbers as well as in the extent of damage caused in every attack. Large organizations operate a Cyber Security Operation Center (CSOC), which forms the first line of cyber-defense. The inspection of cyber-alerts is a critical part of CSOC operations (defender or blue team). Recent work proposed a reinforcement learning (RL) based approach for the defender’s decision-making to prevent the cyber-alert queue length from growing large and overwhelming the defender. In this article, we perform a red team (adversarial) evaluation of this approach. With the recent attacks on learning-based decision-making systems, it is even more important to test the limits of the defender’s RL approach. Toward that end, we learn several adversarial alert generation policies and the best response against them for various defender’s inspection policy. Surprisingly, we find the defender’s policies to be quite robust to the best response of the attacker. In order to explain this observation, we extend the earlier defender’s RL model to a game model with adversarial RL, and show that there exist defender policies that can be robust against any adversarial policy. We also derive a competitive baseline from the game theory model and compare it to the defender’s RL approach. However, when we go further to exploit the assumptions made in the Markov Decision Process (MDP) in the defender’s RL model, we discover an attacker policy that overwhelms the defender. We use a double oracle like approach to retrain the defender with episodes from this discovered attacker policy. This made the defender robust to the discovered attacker policy and no further harmful attacker policies were discovered. Overall, the adversarial RL and double oracle approach in RL are general techniques that are applicable to other RL usage in adversarial environments.

Large organizations typically have Cybersecurity Operations Centers (CSOCs) distributed at multiple locations that are independently managed, and they have their own cybersecurity analyst workforce. Under normal operating conditions, the CSOC locations are ideally staffed such that the alerts generated from the sensors in a work-shift are thoroughly investigated by the scheduled analysts in a timely manner. Unfortunately, when adverse events such as increase in alert arrival rates or alert investigation rates occur, alerts have to wait for a longer duration for analyst investigation, which poses a direct risk to organizations. Hence, our research objective is to mitigate the impact of the adverse events by dynamically and autonomously re-allocating alerts to other location(s) such that the performances of all the CSOC locations remain balanced. This is achieved through the development of a novel centralized adaptive decision support system whose task is to re-allocate alerts from the affected locations to other locations. This re-allocation decision is non-trivial because the following must be determined: (1) timing of a re-allocation decision, (2) number of alerts to be reallocated, and (3) selection of the locations to which the alerts must be distributed. The centralized decision-maker (henceforth referred to as agent) continuously monitors and controls the level of operational effectiveness-LOE (a quantified performance metric) of all the locations. The agent's decision-making framework is based on the principles of stochastic dynamic programming and is solved using reinforcement learning (RL). In the experiments, the RL approach is compared with both rule-based and load balancing strategies. By simulating real-world scenarios, learning the best decisions for the agent, and applying the decisions on sample realizations of the CSOC's daily operation, the results show that the RL agent outperforms both approaches by generating (near-) optimal decisions that maintain a balanced LOE among the CSOC locations. Furthermore, the scalability experiments highlight the practicality of adapting the method to a large number of CSOC locations.

A typical Cybersecurity Operations Center (CSOC) is a service organization. It hires and trains analysts, whose task is to perform analysis of alerts that were generated while monitoring the client’s networks. Due to ever-increasing financial and infrastructure burden on a CSOC driven by the rapidly growing demand for security services, it would become prohibitively expensive to continually expand the size of a CSOC to meet the demands in the future. An alternative solution is to outsource the alert analysis process to on-demand analysts, to provide scalable CSOC service to its clients with features, such as (1) higher throughput, (2) higher quality, and (3) more economical service than the current in-house service. The current outsourcing model is not cost effective and an exact optimization model is computationally inefficient. This article presents a novel two-step sequential mixed integer programming optimization method that is used in the development of a new decision-support business model for outsourcing the alert analysis process. It is demonstrated that through this model, a CSOC can effectively deliver its alert management services with the above-mentioned features. Results indicate that the model is scalable, computationally viable, real-time implementable, and can deliver CSOC services that meet the service-level agreement (SLA) between the CSOC and its client. In addition, the article provides valuable insights into the cost of operating the new business process outsourcing model for cybersecurity services.

Intrusion detection systems (IDSs) analyze data that are collected by sensors, which monitor the network traffic. Any alert generated by the IDS is transmitted to a cybersecurity operations center (CSOC), which performs the important task of analyzing the alerts. In order to deliver a strong security against threats, an efficient CSOC requires the following characteristics: 1) all alerts must be analyzed in a timely manner; 2) there must be an ideal mix of analyst expertise levels in the organization because the quality of analysis performed depends on the mix; and 3) there must be adequate operating budget to hire the required number of analyst personnel. However, it is non-trivial for a CSOC manager to establish the parameter settings for the above characteristics for a desired CSOC efficiency, and current literature lacks a thorough analysis of the tradeoffs between them. This void is filled by this paper whose research objective is to develop an optimized tradeoff study model of the CSOC that studies and quantifies the interactions between the above characteristics, and to use the knowledge gained from the above study to provide the foundation principles to establish and operate an efficient CSOC. A constraint-optimization tradeoff study model is built to drive the decisions that optimize the above characteristics of the CSOC, which is then tested via several simulation runs of the alert arrival and service processes at the CSOC. The paper serves as the first step toward a unified tradeoff study model that integrates the throughput performance, the quality of analysis, and the cost metrics to design and establish an efficient CSOC. Results from the above optimization-simulation tests capture several valuable insights along with parameter settings of the metrics that explain how to operate an efficient CSOC, and quantifies the economic impact of scaling-up the CSOC operation.

A Cyber Security Operations Center (CSOC) is responsible for investigating all the alerts generated from the intrusion detection systems to identify suspicious activities in a timely manner. There exists a critical gap between the time needed (demand) and the time available (limited analyst resource) for alert investigation at a CSOC. Hence, alert prioritization is important, for which CSOCs employ ad-hoc filtering methods to prune and triage the alerts that are presented to the analysts for investigation. One of the major drawbacks of the ad-hoc methods is that they do not comprehensively take into consideration the organization-specific factors such as mission and asset criticality, CSOC resource availability, demand variations, and the desired CSOC performance metrics. Hence, an ad-hoc triaging (or prioritization) method is insufficient, and an intelligent method for optimal selection of alerts that considers the above-mentioned organization-specific factors must be developed, which is described as a two-step process in this paper. First, a composite risk score of each alert is determined using a quantitative value function hierarchy process, which takes into account several organization-specific factors. Second, an optimization model selects a list of alerts for investigation that optimizes the CSOC performance metrics for a given demand subject to its resource constraints. Experimental results show that the alerts that pertain to mission criticalities are handled in a timelier manner as compared to current practices at the CSOCs. The average persistence time of an alert in the CSOC system is also shown to significantly reduce with this new approach, which is a paradigm shift in providing a stronger cyber-defense system by protecting the critical constituents of an organization.

While the Internet of Things (IoT) becomes increasingly popular and ubiquitous, IoT devices often remain unprotected and can be exploited to launch large-scale distributed denial-of-service (DDoS) attacks. One could attempt to employ traditional DDoS defense solutions, but these solutions are hardly suitable in IoT environments since they seldom consider the resource constraints of IoT devices. We present FR-WARD, a system that defends against DDoS attacks launched from an IoT network. FR-WARD operates close to potential attack sources at the gateway of an IoT network and drops packets to throttle any DDoS traffic that attempts to leave the IoT network. However, in order to properly react to traffic too difficult to categorically label as good or bad, FR-WARD employs a novel response based on the fast retransmit and flow control mechanisms of the Transmission Control Protocol (TCP) which minimizes the energy consumption and network latency of benign IoT devices within the policed network. Based on our mathematical analysis, simulation, and experimental evaluation, FR-WARD not only effectively mitigates DDoS traffic, but also minimizes the number of retransmitted packets and the connection durations of benign IoT devices. In fact, FR-WARD can successfully mitigate both naive flood attacks and smarter DDoS attacks that follow TCP congestion control but still reduce overhead caused by retransmitted packets for benign IoT devices by a up to a factor of 150.

Cyber reconnaissance is the process of gathering information about a target network for the purpose of compromising systems within that network. Network-based deception has emerged as a promising approach to disrupt attackers' reconnaissance efforts. However, limited work has been done so far on measuring the effectiveness of network-based deception. Furthermore, given that Software-Defined Networking (SDN) facilitates cyber deception by allowing network traffic to be modified and injected on-the-fly, understanding the effectiveness of employing different cyber deception strategies is critical. In this paper, we present a model to study the reconnaissance surface of a network and model the process of gathering information by attackers as interactions with a cyber defensive system that may use deception. To capture the evolution of the attackers' knowledge during reconnaissance, we design a belief system that is updated by using a Bayesian inference method. For the proposed model, we present two metrics based on KL-divergence to quantify the effectiveness of network deception. We tested the model and the two metrics by conducting experiments with a simulated attacker in an SDN-based deception system. The results of the experiments match our expectations, providing support for the model and proposed metrics.

The analysts at a cybersecurity operations center (CSOC) analyze the alerts that are generated by intrusion detection systems (IDSs). Under normal operating conditions, sufficient numbers of analysts are available to analyze the alert workload. For the purpose of this article, this means that the cybersecurity analysts in each shift can fully investigate each and every alert that is generated by the IDSs in a reasonable amount of time and perform their normal tasks in a shift. Normal tasks include analysis time, time to attend training programs, report writing time, personal break time, and time to update the signatures on new patterns in alerts as detected by the IDS. There are several disruptive factors that occur randomly and can adversely impact the normal operating condition of a CSOC, such as (1) higher alert generation rates from a few IDSs, (2) new alert patterns that decrease the throughput of the alert analysis process, and (3) analyst absenteeism. The impact of the preceding factors is that the alerts wait for a long duration before being analyzed, which impacts the level of operational effectiveness (LOE) of the CSOC. To return the CSOC to normal operating conditions, the manager of a CSOC can take several actions, such as increasing the alert analysis time spent by analysts in a shift by canceling a training program, spending some of his own time to assist the analysts in alert investigation, and calling upon the on-call analyst workforce to boost the service rate of alerts. However, additional resources are limited in quantity over a 14-day work cycle, and the CSOC manager must determine when and how much action to take in the face of uncertainty, which arises from both the intensity and the random occurrences of the disruptive factors. The preceding decision by the CSOC manager is nontrivial and is often made in an ad hoc manner using prior experiences. This work develops a reinforcement learning (RL) model for optimizing the LOE throughout the entire 14-day work cycle of a CSOC in the face of uncertainties due to disruptive events. Results indicate that the RL model is able to assist the CSOC manager with a decision support tool to make better decisions than current practices in determining when and how much resource to allocate when the LOE of a CSOC deviates from the normal operating condition.

Online social network (OSN) discussion groups are exerting significant effects on political dialogue. In the absence of access control mechanisms, any user can contribute to any OSN thread. Individuals can exploit this characteristic to execute targeted attacks, which increases the potential for subsequent malicious behaviors such as phishing and malware distribution. These kinds of actions will also disrupt bridges among the media, politicians, and their constituencies. For the concern of Security Management, blending malicious cyberattacks with online social interactions has introduced a brand new challenge. In this paper we describe our proposal for a novel approach to studying and understanding the strategies that attackers use to spread malicious URLs across Facebook discussion groups. We define and analyze problems tied to predicting the potential for attacks focused on threads created by news media organizations. We use a mix of macro static features and the micro dynamic evolution of posts and threads to identify likely targets with greater than 90% accuracy. One of our secondary goals is to make such predictions within a short (10 minute) time frame. It is our hope that the data and analyses presented in this paper will support a better understanding of attacker strategies and footprints, thereby developing new system management methodologies in handing cyber attacks on social networks.

Cybersecurity threats are on the rise with evermore digitization of the information that many day-to-day systems depend upon. The demand for cybersecurity analysts outpaces supply, which calls for optimal management of the analyst resource. Therefore, a key component of the cybersecurity defense system is the optimal scheduling of its analysts. Sensor data is analyzed by automatic processing systems, and alerts are generated. A portion of these alerts is considered to be significant , which requires thorough examination by a cybersecurity analyst. Risk, in this article, is defined as the percentage of unanalyzed or not thoroughly analyzed alerts among the significant alerts by analysts. The article presents a generalized optimization model for scheduling cybersecurity analysts to minimize risk (a.k.a., maximize significant alert coverage by analysts) and maintain risk under a pre-determined upper bound. The article tests the optimization model and its scalability on a set of given sensors with varying analyst experiences, alert generation rates, system constraints, and system requirements. Results indicate that the optimization model is scalable and is capable of identifying both the right mix of analyst expertise in an organization and the sensor-to-analyst allocation in order to maintain risk below a given upper bound. Several meta-principles are presented, which are derived from the optimization model, and they further serve as guiding principles for hiring and scheduling cybersecurity analysts. The simulation studies (validation) of the optimization model outputs indicate that risk varies non-linearly with an analyst/sensor ratio, and for a given analyst/sensor ratio, the risk is independent of the number of sensors in the system.

An important component of the cyber-defense mechanism is the adequate staffing levels of its cybersecurity analyst workforce and their optimal assignment to sensors for investigating the dynamic alert traffic. The ever-increasing cybersecurity threats faced by today’s digital systems require a strong cyber-defense mechanism that is both reactive in its response to mitigate the known risk and proactive in being prepared for handling the unknown risks. In order to be proactive for handling the unknown risks, the above workforce must be scheduled dynamically so the system is adaptive to meet the day-to-day stochastic demands on its workforce (both size and expertise mix). The stochastic demands on the workforce stem from the varying alert generation and their significance rate, which causes an uncertainty for the cybersecurity analyst scheduler that is attempting to schedule analysts for work and allocate sensors to analysts. Sensor data are analyzed by automatic processing systems, and alerts are generated. A portion of these alerts is categorized to be significant , which requires thorough examination by a cybersecurity analyst. Risk, in this article, is defined as the percentage of significant alerts that are not thoroughly analyzed by analysts. In order to minimize risk, it is imperative that the cyber-defense system accurately estimates the future significant alert generation rate and dynamically schedules its workforce to meet the stochastic workload demand to analyze them. The article presents a reinforcement learning-based stochastic dynamic programming optimization model that incorporates the above estimates of future alert rates and responds by dynamically scheduling cybersecurity analysts to minimize risk (i.e., maximize significant alert coverage by analysts) and maintain the risk under a pre-determined upper bound. The article tests the dynamic optimization model and compares the results to an integer programming model that optimizes the static staffing needs based on a daily-average alert generation rate with no estimation of future alert rates (static workforce model). Results indicate that over a finite planning horizon, the learning-based optimization model, through a dynamic (on-call) workforce in addition to the static workforce, (a) is capable of balancing risk between days and reducing overall risk better than the static model, (b) is scalable and capable of identifying the quantity and the right mix of analyst expertise in an organization, and (c) is able to determine their dynamic (on-call) schedule and their sensor-to-analyst allocation in order to maintain risk below a given upper bound. Several meta-principles are presented, which are derived from the optimization model, and they further serve as guiding principles for hiring and scheduling cybersecurity analysts. Days-off scheduling was performed to determine analyst weekly work schedules that met the cybersecurity system’s workforce constraints and requirements.

Outlier or anomaly detection in large data sets is a fundamental task in data science, with broad applications. However, in real data sets with high-dimensional space, most outliers are hidden in certain dimensional combinations and are relative to a user's search space and interest. It is often more effective to give power to users and allow them to specify outlier queries flexibly, and the system will then process such mining queries efficiently. In this study, we introduce the concept of query-based outlier in heterogeneous information networks, design a query language to facilitate users to specify such queries flexibly, define a good outlier measure in heterogeneous networks, and study how to process outlier queries efficiently in large data sets. Our experiments on real data sets show that following such a methodology, interesting outliers can be defined and uncovered flexibly and effectively in large heterogeneous networks.

In the real world, various systems can be modeled using heterogeneous networks which consist of entities of different types. Many problems on such networks can be mapped to an underlying critical problem of discovering top-K subgraphs of entities with rare and surprising associations. Answering such subgraph queries efficiently involves two main challenges: (1) computing all matching subgraphs which satisfy the query and (2) ranking such results based on the rarity and the interestingness of the associations among entities in the subgraphs. Previous work on the matching problem can be harnessed for a naïve ranking-after-matching solution. However, for large graphs, subgraph queries may have enormous number of matches, and so it is inefficient to compute all matches when only the top-K matches are desired. In this paper, we address the two challenges of matching and ranking in top-K subgraph discovery as follows. First, we introduce two index structures for the network: topology index, and graph maximum metapath weight index, which are both computed offline. Second, we propose novel top-K mechanisms to exploit these indexes for answering interesting subgraph queries online efficiently. Experimental results on several synthetic datasets and the DBLP and Wikipedia datasets containing thousands of entities show the efficiency and the effectiveness of the proposed approach in computing interesting subgraphs.

Mining outliers in a heterogeneous information network is a challenging problem: It is even unclear what should be outliers in a large heterogeneous network (e.g., Outliers in the entire bibliographic network consisting of authors, titles, papers and venues). In this study, we propose an interesting class of outliers, query-based sub network outliers: Given a heterogeneous network, a user raises a query to retrieve a set of task-relevant sub networks, among which, sub network outliers are those that significantly deviate from others (e.g., Outliers of author groups among those studying "topic modeling"). We formalize this problem and propose a general framework, where one can query for finding sub network outliers with respect to different semantics. We introduce the notion of sub network similarity that captures the proximity between two sub networks by their membership distributions. We propose an outlier detection algorithm to rank all the sub networks according to their outlierness without tuning parameters. Our quantitative and qualitative experiments on both synthetic and real data sets show that the proposed method outperforms other baselines.

Performance monitor software for data centers typically generates a great number of alert sequences. These alert sequences indicate abnormal network events. Given a set of observed alert sequences, it is important to identify the most critical alerts that are potentially the causes of others. While the need for mining critical alerts over large scale alert sequences is evident, most alert analysis techniques stop at modeling and mining the causal relations among the alerts.

In the real world, various systems can be modeled using heterogeneous networks which consist of entities of different types. People like to discover groups (or cliques) of entities linked to each other with rare and surprising associations from such networks. We define such anomalous cliques as Association-Based Clique Outliers (ABCOutliers) for heterogeneous information networks, and design effective approaches to detect them. The need to find such outlier cliques from networks can be formulated as a conjunctive select query consisting of a set of (type, predicate) pairs. Answering such conjunctive queries efficiently involves two main challenges: (1) computing all matching cliques which satisfy the query and (2) ranking such results based on the rarity and the interestingness of the associations among entities in the cliques. In this paper, we address these two challenges as follows. First, we introduce a new low-cost graph index to assist clique matching. Second, we define the outlierness of an association between two entities based on their attribute values and provide a methodology to efficiently compute such outliers given a conjunctive select query. Experimental results on several synthetic datasets and the Wikipedia dataset containing thousands of entities show the effectiveness of the proposed approach in computing interesting ABCOutliers.

The nodes in wireless sensor networks (WSNs) utilize the radio frequency (RF) channel to communicate. Given that the RF channel is the primary communication channel, many researchers have developed techniques for securing that channel. However, the RF channel is not the only interface into a sensor. The sensing components, which are primarily designed to sense characteristics about the outside world, can also be used (or misused) as a communication (side) channel. In this paper, we characterize the side channels for various sensory components (i.e., light sensor, acoustic sensor, and accelerometer). While previous work has focused on the use of these side channels to improve the security and performance of a WSN, we seek to determine if the side channels have enough capacity to potentially be used for malicious activity. Specifically, we evaluate the feasibility and practicality of the side channels using today's sensor technology and illustrate that these channels have enough capacity to enable the transfer of common, well-known malware. The ultimate goal of this work is to illustrate the need for intrusion detection systems (IDSs) that not only monitor the RF channel, but also monitor the values returned by the sensory components.

Cyber analysis is a difficult task for analysts due to huge amounts of noise-abundant monitoring data and increasing complexity of the reasoning tasks. Therefore, experience from experts can provide guidance for analysts' analytical reasoning and contribute to training. Despite its great potential benefits, experience has not been effectively leveraged in the existing reasoning support systems due to the difficulty of elicitation and reuse. To fill the gap, we propose an experience-aided reasoning support system which can automatically capture experts' experi-ence and subsequently guide the novices' reasoning in a step-by-step manner. Drawing on cognitive theory, we model experience as a reasoning process involving “actions”, “observations”, and “hypotheses”. Computability and adaptability are the compar-ative advantages of this model: the “hypotheses” capture analysts' internal mental reasoning as a black box, while the “actions” and “observations” formally representing the external context and analysts' evidence exploration activities. This paper demonstrates how this system, built on this experience model, can capture and utilize experience effectively.

In wireless sensor networks, compromised sensor nodes can inject false data during both data aggregation and data forwarding. The existing false data detection techniques consider false data injections during data forwarding only and do not allow any change on the data by data aggregation. However, this paper presents a data aggregation and authentication protocol, called DAA, to integrate false data detection with data aggregation and confidentiality. To support data aggregation along with false data detection, the monitoring nodes of every data aggregator also conduct data aggregation and compute the corresponding small-size message authentication codes for data verification at their pairmates. To support confidential data transmission, the sensor nodes between two consecutive data aggregators verify the data integrity on the encrypted data rather than the plain data. Performance analysis shows that DAA detects any false data injected by up toTcompromised nodes, and that the detected false data are not forwarded beyond the next data aggregator on the path. Despite that false data detection and data confidentiality increase the communication overhead, simulation results show that DAA can still reduce the amount of transmitted data by up to 60% with the help of data aggregation and early detection of false data.

Wireless surveillance sensor networks are often required to track multiple targets accurately, especially when the targets come close to each other at so-called mixing regions. This research presents eTrack protocol to address the following two problems for a number of targets and their mixing region: (i) which sensor nodes should be scheduled to sense a particular event such that targets are tracked accurately, and (ii) which pair of tracks passing through the mixing region belong to a particular target. To tackle the scheduling problem, eTrack introduces a first-of-its-kind closed-loop coverage control technique that allocates resources of sensor nodes for each target in proportion with its required tracking accuracy. To handle the identity management problem, eTrack exploits the fact that targets prefer certain paths through a mixing region and takes advantage of the spatio-temporal correlation of events detected by different sensor nodes within the mixing region for the same target. Simulation results that eTrack significantly reduces the computation and communication overhead with mixing regions while achieving better tracking accuracy than existing multiple target tracking techniques.

In next generation wireless networks, system resources such as transmission power and channelization codes should be allocated efficiently and fairly to individual transmissions. Efficient assignment of channelization codes such as orthogonal variable spreading factor (OVSF) codes in WCDMA-based cellular networks is crucial in supporting the delay and rate guarantees of real-time flows. However, OVSF codes support data rates that are powers of two and do not support many intermediate data rates. This reduces some flexibility in the allocation of code resources, and under poor channel conditions it may result in over-provisioning a real-time flow as well as under-provisioning a non-real-time flow. Nonblocking OVSF (NOVSF) codes can, however, support many intermediate data rates. This paper proposes an NOVSF code/time-slot allocation algorithm to achieve better system utilization and better flexibility in code allocation. Simulation results show that when compared to OVSF codes, the use of NOVSF codes reduces the call blocking probability of real-time flows and provides better overall throughput for non-real-time flows.

Wireless sensor networks are often densely deployed to prolong their lifetime by rotating the subset of nodes that are put on duty. This paper addresses the following two problems: Given the required miss-ratios for multiple events, (i) which subset of nodes should be put on duty for each event to assure its event miss-ratio?, and (ii) how should those on-duty nodes encode their data with minimum overhead of source coding and maximum energy saving? We propose CORA protocol which activates sensor nodes and assigns their rates jointly based on dynamically changing probability of event occurrences. The on-duty sensor nodes are assigned different rates based on whether they are located at hot spots or not. Those sensor nodes that are located at the hot spots are made active dynamically by CORA in such a way that proportional fairness is achieved in providing their miss-ratio guarantees. Simulation results show that CORA meets event miss-ratio assurances fairly and achieves high source coding gain with negligible overhead of correlation information maintenance.

This paper presents a route recovery scheme called route recovery by one-hop broadcast (RROB) that removes compromised nodes from the current route and reconstructs the route without depending on central mediation. The basic idea behind RROB is that a new path between the source node and the destination is reconstructed by having the current path bypass the compromised nodes. RROB's route establishment is based on adjacency matrices which give connectivity information between nodes to prevent packet flooding in the network. Instead of flooding packets in the network, RROB utilizes the neighbors of the compromised nodes to bypass the compromised nodes. The length of bypass is adjusted by the number of compromised nodes and the required security level. RROB is a pure local route recovery protocol and the protocol works regardless of the number of compromised nodes on the routing path. RROB's overhead of route reestablishment is restricted within one-hop neighborhood of the compromised nodes and therefore shows as high as 24% energy savings compared to existing schemes, while route establishment shows shorter latency.

In wireless sensor networks, the data collected by neighboring sensor nodes show high correlation. To exploit the data correlation for reducing the amount of data while transmitting data from sensor nodes to their base station, this paper introduces multiple-input turbo (MIT) code to implement a joint source coding and data aggregation. If there exists an explicit communication between two sensor nodes, their correlated data bits are first interleaved with each other in accordance with their correlation relation, and then are encoded and punctured. On the other hand, if there is no direct communication between sensor nodes, the data sequences are encoded with respect to side information based on the distributed source coding principles. Whenever the bit error rate needs to be improved, MIT code is used for channel coding as well. MIT code employs partial interleaving to reduce energy consumption and memory size requirements for even small-size information blocks. The simulation results show that the bit error rate performance of MIT code outperforms turbo codes to some extent, even if MIT code implements partial interleaving on interleavers.

This paper presents a symmetric key establishment protocol, called event-based reconciliation (ERS), that does not require sensor nodes to store pairwise keys prior to deployment. The novel idea behind ERS is to establish symmetric keys by exchanging the secret key information via distributed source coding that uses some event data as side information. Any two neighboring sensor nodes that are able to detect the same event first exchange some key information using distributed source coding and data of the event detected in the overlapping sensing region, and reconcile a symmetric key in two iterations. A key expansion algorithm is also presented to enhance the recovery of key bits in the presence of bit errors and to improve the secrecy of the key establishment. Performance evaluation results show that ERS has low memory and communication overhead compared to previous symmetric key distribution schemes

This paper addresses event miss-ratio statistical assurances for data gathering in cluster based dense wireless sensor networks. In line with recent commercial off-the-shelf sensor nodes, this paper considers sensor nodes with multiple sensing units and power modes of operation. Such sensor nodes are usually unable to process the data generated by multiple sensing units simultaneously, thereby resulting in event misses. We present an adaptive task scheduling protocol, called ASPEN, for providing event miss-ratio statistical assurances in wireless sensor networks. ASPEN consists of two coarse-grain task scheduling algorithms at the cluster-level and one fine-grain task scheduling algorithm at the node level. The first coarse-grain scheduling algorithm eliminates misses during event processing by assigning each sensor node the minimum number of event types to observe. The other coarse-grain scheduling algorithm enables accurate transfer of data from sensor node to the cluster-head for each event type while ensuring that less redundant data are transmitted. The proposed fine-grain scheduling algorithm determines the order of data processing for multiple sensing units, chooses appropriate power modes to avoid event misses, and takes the effect of environmental factors such as temperature on the sensing ability of the nodes into account. Simulation results show that, with sufficient node redundancy, ASPEN can provide statistical assurances for event miss-ratio while reducing the amount of event data transmitted up to 65%

This paper proposes a secure data aggregation and source-channel coding algorithm, called SAC, for implementing secure data aggregation and compression along with error correction in wireless sensor networks by employing multiple-input turbo (MIT) code that we have recently introduced for source and channel coding. If there is no direct communication between two sensor nodes, SAC implements Slepian-Wolf coding principles in performing source encoding using MIT code. However, if there exists an explicit communication between two sensor nodes, the node that has more residual energy performs data aggregation and source encoding. When the bit error rate is not acceptable, MIT code is used for channel coding as well. Security is achieved by encrypting the data with shared keys. To reduce energy consumption, latency, and memory size requirements, MIT code employs partial interleavers.

It is critical to design efficient power management and scheduling techniques for wireless sensor nodes that operate with limited battery power. The design of these techniques becomes more challenging especially when each sensor node has multiple sensing units and the occurrences of their events of interest are not known in advance. This paper proposes an event-driven task scheduling algorithm, called MSUS (multiple sensing unit scheduling). MSUS determines the best power state based on the timing and priority requirements, the event-misses, and the existing and the predicted future tasks for all the sensing units of a sensor node with multiple sensing units. Simulation results show that MSUS leads energy savings up to 49% and reduces event misses by 56% when compared to the greedy technique that puts the sensor node components into the lowest power consumption level whenever there is no available task to process.

Abstract — A sensor node with multiple sensing units is usually unable to process simultaneously the data generated by multiple sensing units, thereby resulting in event misses. This paper presents a collaborative task scheduling algorithm, called CTAS, to minimize event misses and energy consumption by exploiting power modes and overlapping sensing areas of sensor nodes. The novel idea of CTAS lies in that it employs a two-level scheduling approach to the execution of tasks collaboratively at group and individual levels among neighboring sensor nodes. CTAS first implements coarse-grain scheduling at the group level to schedule the event types to be detected by each group member. Then, CTAS performs fine-grain scheduling to schedule the tasks corresponding to the assigned event types. The coarse grain scheduling of CTAS is based on a new algorithm that determines the degree of overlapping among neighboring sensor nodes. Simulation results show that CTAS yields significant improvements in energy consumption up to 67 % and reduction in event misses by 75%. I.

This paper proposes a new scheduling scheme that exploits multiuser diversity to improve the shared channel utilization and the downlink capacity of the cell by reducing the intra cell interference in CDMA based cellular networks with relays. The scheduling algorithm accomplishes this by choosing a one hop (base station to mobile) or two hop(base station to relay and then from relay to mobile) path that yields the best channel throughput while using low transmission power for the shared channel. The reduction in transmission power(cost) for the shared channel reduces the total base station transmit power, thus reducing the multi-access interference and improving the downlink capacity. Simulation results show that by making use of relays the proposed scheduling scheme improves the throughput and channel conditions of the users on the shared channel and at the same time reduces the interference for other users.

Rearrangeable networks can realize each and every permutation in one pass through the network. Shuffle-exchange networks provide an efficient interconnection scheme for implementing various types of parallel processes. Whether (2n)-stage shuffle-exchange networks with N= 2 n inputs/outputs are rearrangeable has remained an open question for approximately three decades. This question has been answered affirmatively in this paper. An important corollary of the main result is the proof that two passes through an Omega network are sufficient and necessary to implement any permutation. In obtaining the main results of this paper, frames that look like grids with horizontal links of different lengths are shown to be remarkable tools for identifying and characterizing the binary matrix representations of permutations.

This paper proposes a dynamic channel and packet assignment (DCPA) scheme to serve efficiently circuit-switching (e.g., voice traffic) and packet-switching (e.g., Internet traffic) communications in wireless cellular networks. The DCPA, as a distributed-controlled scheme, assigns channels or packet-slots to handoff and new calls based on their traffic type and channel status of cells. Simulation results, based on a circuit-switching and packet-switching traffic model, show that the DPCA scheme provides better QoS than a dynamic channel allocation scheme designed for circuit-switching communications only.

This paper presents a hardware-efficient memory allocation (EMA) technique designed to eliminate both internal and external fragmentation that appear in the buddy system. EMA can allocate a free memory block of any size in any part of memory. Hardware implementation of EMA is introduced, but only part of its circuits is shown in the paper due to the space limitation. Simulation results show that EMA utilizes memory space more efficiently than the previously known techniques.

The work performed by a parallel algorithm is the product of its running time and the number of processors it requires. This paper presents work-efficient (or cost-optimal) routing algorithms to determine the switch settings for realizing permutations on rearrangeable symmetrical networks such as Benes and the reduced /spl Omega//sub N//spl Omega//sub N//sup -1/. These networks have 2n-1 stages with N=2/sup n/ inputs/outputs, each stage consisting of N/2 crossbar switches of size (2/spl times/2). Previously known parallel routing algorithms for a rearrangeable network with N inputs determine the states of all switches recursively in O(n) iterations using N processors. Each iteration determines the switch settings of at most two stages of the network and requires at least O(n) time on a computer of N processors, regardless of the type of its interconnection network. Hence, the work of any previously known parallel routing algorithm equals at least O(Nn/sup 2/) for setting up all the switches of a rearrangeable network. The new routing algorithms run on a computer of p processors, 1/spl les/p/spl les/N/n, and perform work O(Nn). Moreover, because the range of p is large, the new routing algorithms do not have to be changed in case some processors become faulty.

Bandwidth-intensive and delay-sensitive applications demand ATM technology to be brought into every desktop. However, it is very costly in terms of both hardware and software to replace a traditional LAN such as Ethernet and token ring by an ATM network. Therefore, internetworking LANs with an ATM backbone network is considered a cost-effective and most promising solution for bringing ATM into the mainstream. To sustain delay-sensitive applications (e.g., video or voice) and loss-sensitive applications (e.g., data transfer), this paper presents a slotted-ring network (SRN) with spatial reuse. A simple priority-based access protocol, called the check request before send (CRBS), for providing nonpreemptive multipriority services over SRN is described. SRN provides communication among an ATM switch, ATM stations, and internetworking units connected to legacy LANs. Any node of SRN in the CRBS protocol determines whether it can use a slot, without requiring any authorization or an exchange of message with the other nodes. The CRBS protocol reduces the unfairness features associated with any slotted-ring network. An analytical model is presented to analyze the CRBS protocol under Poisson input traffic and uniform output traffic. Extensive simulations are run to assess the performance of the CRBS protocol for two classes of cells with priorities 0 and 1. The analytical performance results are shown to be close to those obtained by simulations.

A multistage self-routing permutation network is presented. This network is constructed from concentrators and digit-controlled 2/spl times/4 switches. A destination-tag routing scheme is used to realize any arbitrary permutation. The network has O(log/sup 2/ N) gate-delay and uses O(N/sup 2/) VLSI-area, where N is the number of inputs. Assuming packet-switching is used for message transmission, the delay and VLSI-area of the network are smaller than those of any self-routing permutation network presented to date.>

Rearrangeable multistage networks such as the Benes network realize any permutation, yet their routing algorithms are not cost-effective. On the other hand, there exist inexpensive routing algorithms for nonrearrangeable networks, but no simple technique exists to characterize all the permutations realized on these networks. This paper introduces the concept of frame and shows how it can be used to characterize all the permutations realized on various multistage interconnection networks. They include subnetworks of baseline, Benes, and cascaded baseline and shuffle-exchange networks.>