The expansion of Intelligent Transportation Systems (ITS) and their integration into Vehicular Adhoc Networks (VANETs) bring a number of critical safety and security concerns. Among many is the false reporting attack, in which a malicious actor sends adversarial messages to fabricate artificial traffic incidents. To ensure safety and reliability, addressing false alert attacks is particularly crucial due to the potential danger that this type of attack poses. False alerts may cause vehicles to take unnecessary evasive maneuvers to avoid non-existent hazards, which might lead to accidents and endanger the safety of drivers, passengers, and other road users. In this research, we aim to address this threat of false alert attacks in VANETs by using the VeReMiAP Dataset (a VeReMi-based dataset) as a benchmark and develop machine learning (ML) models and approaches to detect and mitigate false alert attacks in VANETs. The methodology includes a detailed analysis of the dataset, feature engineering in conjunction with plausibility, and the use of state-of-the-art ML models for detection. The research findings show that the proposed approach can effectively detect false alert attacks in VANETs. The results show that this approach is effective for detecting the attack with high accuracy and F1 score. The research also provides insights into the performance of different ML models and the importance of feature engineering in detecting false alert attacks. The research findings can be used to develop more robust and reliable security mechanisms to ensure the safety and security of road users.

Cooperative Intelligent Transport Systems (C-ITS) are helping to improve road safety and traffic efficiency by enabling vehicles to exchange data in real time through wireless communication. Collective Perception Services (CPS) is an important component of C-ITS, where vehicles collaborate to provide each other with a richer understanding of their environment. CPS provides tremendous benefits; however, it is critically dependent on the integrity of the data transmitted by participating vehicles. Data falsification attacks, where misbehaving vehicles insert false information in transmitted packets, can seriously impact vehicle safety. This paper proposes a machine learning (ML)-based method for detecting data falsification attacks in C-ITS using the SimCPS dataset. The model learns attack patterns from the data itself instead of using typical rule-based approaches currently available in the literature. Our preliminary results indicate that the proposed model can significantly outperform existing approaches in terms of detection accuracy and lower false positive rates.

In vehicular ad hoc networks (VANETs), vehicles exchange sensitive information, including vehicle identity, position, speed, heading and other parameters, with nearby vehicles or infrastructure through Basic Safety Messages (BSM). However, VANET communication is vulnerable to various types of attacks, and appropriate security mechanisms must be in place to ensure that exchanged messages are not altered or false messages created by malicious attackers. In this paper, we propose a new transfer learning (TL) based technique for detecting different types of denial-of-service (DoS) attacks in vehicle-to-vehicle (V2V) communication. We start with a pre-trained CNN-BiLSTM model, which was trained to detect various types of attacks in internet traffic. We update the model by training the LSTM layers, while keeping the weights of the CNN layers unchanged. The proposed TL approach is not only able to detect malicious BSMs/senders with higher accuracy but also requires less training time compared to the same DL algorithms with no transfer learning. Simulation results demonstrate that our approach outperforms the existing techniques for each of the different types of DoS attacks in the VeReMi extension dataset in terms of accuracy, precision, recall and F1-score.

Vehicular Ad-Hoc Network(VANET) is an emerging wireless technology vital to the Intelligent Transportation System(ITS), which aims to mitigate traffic problems and improve road safety. Many VANET safety applications rely on the periodic broadcast of vehicle status information in the form of Basic Safety Messages (BSMs). When the vehicle density increases, the wireless channel faces congestion resulting in unreliable safety applications. Various decentralized congestion control algorithms have been proposed to effectively decrease channel congestion by controlling transmission parameters such as message rate, transmission power, and data rate. This paper proposes a data rate-based congestion control technique using the Q-Learning algorithm to maintain the channel load below the target threshold. The congestion problem is formulated as a Markov Decision Process (MDP) and solved using a Q-learning algorithm. The goal is to select the most appropriate data rate when transmitting a BSM such that the channel load remains at an acceptable level. Data obtained from a simulated dynamic traffic environment is used to train the Q-Learning algorithm. Our results indicate that the proposed algorithm is able to achieve the target channel load while reducing packet loss compared to existing data rate-based approaches.

Connected and Autonomous Vehicles (CAVs) will play a critical role in improving the safety and efficiency of future Intelligent Transportation System (ITS). Periodic broadcasts of basic safety messages (BSMs) containing up-to-date vehicle status information constitute one important class of inter-vehicular communication. If false or inaccurate information is inserted in the BSMs it can lead to serious consequences such as accidents resulting in bodily injury and even loss of life. In this paper, we propose a machine learning based approach for automatically detecting replay attacks, where BSMs received from neighboring vehicles are rebroadcast, with false sender information, by a malicious node. Simulations using the publicly available Vehicular Reference Misbehavior (VeReMi) extension dataset demonstrate that the proposed model clearly outperforms existing techniques for detecting BSM replay attacks.

Although connected mymargin autonomous vehicles (CAVs) hold great potential to improve driving safety and experience significantly, cybersecurity remains a critical concern. As the de-facto standard for in-vehicle networks, the Controller Area Network (CAN) carries messages and commands vital to the operation of the vehicle. However, due to a lack of security mechanisms, intruders are able to conduct devastating attacks on drivers and passengers over CAN. In order to safeguard CAVs, an Intrusion Detection System (IDS) can be deployed to monitor CAN network activities and detect suspicious behavior resulting from an attack. This paper proposes a prediction-based IDS framework for detecting anomalies and attacks on a CAN bus using temporal correlation of message contents. Two candidates are introduced as the prediction module. The first network is an LSTM that predicts time series data separately for each CAN ID, and the second is a ConvLSTM that predicts messages using correlated data of several CAN IDs. An attack is classified according to prediction errors by a Gaussian Naïve Bayes classifier. The proposed IDS is evaluated against other state-of-the-art one-class classifiers, including OCSVM, Isolation Forest, and Autoencoder, and three existing works, including ReducedInception-ResNet, NeuroCAN, and CANLite, using a real-world dataset, the Car Hacking Dataset. A comparison between the two suggested architectures and their use cases is given. Compared to baseline methods and related studies, the proposed method is shown to be more accurate and can achieve F-scores and detection accuracy of almost 100%.

Vehicular ad hoc networks (VANETs) require timely delivery of periodic basic safety messages (BSMs) containing critical vehicle status information, as well as event-driven notifications to ensure road safety and improve traffic flow. The limited channel capacity of the wireless medium and high message rates needed for adequate situational awareness create a dilemma between the conflicting goals of congestion control and awareness control algorithms. To ensure reliable delivery, vehicles need to interact with a complex and dynamic environment to determine the appropriate message rate and power for their transmissions at any given time. In this paper, we propose an innovative framework where vehicles use reinforcement learning (RL) to intelligently select their transmission parameters based on the current channel conditions. Our simulation results indicate that RL methods can provide a flexible solution for adaptive congestion control by designing the appropriate reward function.

A vehicular ad-hoc network (VANET) consists of moving and stationary vehicles, along with supporting infrastructure, which communicate with each other through a wireless medium. VANETs are an essential component of an Intelligent Transportation System, which aims to reduce road accidents and traffic congestion and provide additional services for drivers in future smart cities. VANET communication is vulnerable to various attacks and cryptographic techniques are used for message integrity and authentication of vehicles in order to ensure security and privacy for vehicular communications. Such approaches have been shown to be effective for outside attacks, where attackers do not have the credentials to participate in the network. However, if there is an inside attacker additional measures are necessary to ensure the correctness of the transmitted data. Position falsification is an attack where the attacker broadcasts a false position, which can lead to increased traffic congestion or even accidents. Therefore, it is imperative to detect such attacks quickly to ensure safety of all participants in the network. Several trust-based models have been proposed for this in the past. This paper proposes a novel and efficient data-centric approach to detect location spoofing, using machine learning algorithms. We have compared our proposed approach with several existing techniques using the VeReMi dataset and shown that its results improved performance in terms of detection accuracy and other key metrics.

Automation has become indispensable in all walks of everyday life. In driving environments, Automated Driving Systems (ADS) aid the driver by reducing the required workload and by improving road safety. These systems require human drivers to remain vigilant and maintain supervisory control over ADS. Therefore, the cognitive attention of the drivers must be estimated accurately for the safe adoption of ADS. Because of the non-invasive recording setup used in low-cost infrared eye-trackers, pupil size measurements are increasingly becoming applicable in the estimation of cognitive load. However, pupil size measurements are highly noisy, resulting in the poor classification of cognitive load levels. In this paper, we propose a methodology for improved classification of changes in cognitive load through the introduction of a state-space model-based approach to filter the pupil size data. The proposed approach was demonstrated on data collected from 16 participants while they performed driving task and several secondary tasks that are designed to emulate three different levels of driving distraction.

The Internet of Vehicles (IoV) and vehicular clouds use sensor data and information from vehicles to implement an intelligent transportation system for future smart cities. The tremendous amount of data generated in IoV can lead to channel congestion, packet loss and delay of time-sensitive messages. This can have a serious impact on the performance of applications and services provided by a vehicular network, particularly safety applications that are time critical. As such, network congestion control is an topic in vehicular networks and various methods of controlling the message transmission rate and power have been explored to-date. In this paper we have proposed a new distributed congestion control algorithm which manipulates the transmission power based on a density estimation derived from the vehicle’s driving speed. The results indicate that the proposed approach is effective in reducing packet loss and improving the relevance of the received messages.

Vehicular Ad Hoc Network (VANET) is a mobile network formed by vehicles, road side units, and other in-frastructures that enable communication between the nodes to improve road safety and traffic control. While this technology promises great benefits to drivers, there are many security and privacy concerns that must be addressed before it can be fully adopted. It is essential to ensure that vehicles participating in the network are authenticated and held accountable in case of misbehaviour. On the other hand, there should be adequate mechanisms for preserving the privacy of vehicles and drivers, so they are protected against unauthorized tracking and release of private information. Many current VANET technologies also depend on a central trusted authority that becomes a single point of failure for the network. In this paper, we propose a new blockchain based decentralized authentication approach for VANET. In this scheme vehicles maintain conditional anonymity in the network and their real identities can only be revealed to authorized entities. Using the blockchain technology, we create a distributed framework and maintain an immutable record of the data, strengthening the integrity of the system. We use the Hyperledger Fabric, a permissioned blockchain technology, to implement our approach and compare its performance to the traditional PKI based method for VANET authentication.

One of the main challenges for communication in Vehicular Ad Hoc Networks (VANETs) is efficient network channel utilization for the transmission of network packets. With the growing number of vehicles in the network, the number of safety messages increases quickly, which results in the network channel congestion. In this paper, we introduce anew approach to adapt the transmission power, which is based on the vehicle density of the network. The aim is to reduce congestion on the network channel and improve the overall performance of network. Our simulation results indicate that this approach can lead to enhanced performance in terms of reduced packet loss and inter-packet delay.

The use of pseudonyms has been proposed in VANETs to enhance location privacy of users. In order to prevent tracking, the pseudonyms associated with a vehicle must be changed frequently. A pseudonym change strategy (PCS) determines the conditions under which pseudonyms should change. An effective PCS is critical for maintaining the privacy of vehicles. Many different PCS have been proposed in recent years. It is important to study the performance of these PCS against intelligent and realistic attacker(s), before actual deployment in vehicles. In this paper, we propose a novel technique for attacker placement and compare the performance of different PCS, using the proposed placement schemes as well as random placement. We also evaluate PCS under different attacker capabilities and traffic conditions. Results indicate that the intelligent attacker placement can have a significant impact on tracking success and can be used to highlight vulnerabilities of a PCS under different traffic conditions.

Cloud computing depends critically on large data centers connected by a high-speed optical network. A fault-tolerant communication scheme to handle requests for communication in such a system is essential. In this paper we have proposed an optimal approach to the problem of developing a path-protection scheme to handle communication requests in data center (DC) networks. We have formulated our problem as an Integer Linear Program (ILP). We have studied our approach using simulations, varying parameters, such as the number of DCs, and the number of disasters. Our simulations show that considering additional disasters do not add significantly to the cost of the solution, which means significant resource savings while supporting users' demands.

Optical grids are emerging as a natural, cost-effective platform to meet the needs for powerful computing, large storage capacity and high-speed data transmission capabilities in a number of important application areas. In spite of the lower power cost per bit of optical networks, it is expected that one of the most challenging issues in the next decade will be reducing the power requirement for such core networks. Much of the recent work on optical grid network design has focused on optimizing the use of traditional computing and network resources in an integrated manner. In grid systems, it is typically possible to select one out of a number of possible destinations to execute a specific job. This is known as anycasting, and in this paper we propose a new approach for energy minimization in optical grids that exploits the inherent flexibility of anycasting. We present a comprehensive integer linear program (ILP) formulation that selects the destination node and performs routing and wavelength assignment (RWA) to minimize the overall energy consumption of a set of static lightpath demands. We also present a 2-stage ILP that can quickly generate solutions for large networks. Simulation results indicate that significant energy savings can be achieved by the proposed approach, not only compared to traditional RWA techniques but also over energy-aware unicast methods.

In hierarchical sensor networks, higher powered relay nodes can be deployed to act as cluster heads. The lifetime of such a network is primarily determined by the lifetime of the relay nodes. Recently, it has been shown that the use of a Mobile Data Collector (MDC), which moves through the sensor network to collect data, can improve the performance of the network in a number of ways. We propose a model for hierarchical networks using a MDC, where the MDC travels along a pre-determined trajectory at a known speed, and collects data from each relay node. In this model, the relay nodes need to buffer their data until they can be uploaded to the MDC. To reduce the buffer size, as well as the delay for the data communication, it is desirable to minimize the length of the trajectory. In our model the MDC "visits" a relay node, to collect data, at any point within the permitted transmission distance of the relay node. There is a trade-off in this approach, as a large permitted transmission distance means that the relay node will expend higher energy, and hence, have a reduced lifetime. In this paper, we present two formulations for computing the minimal trajectory of the MDC. Our approaches allow us to control the transmission distances of the relay nodes and hence, achieve the lifetime objectives. Minimizing the length of the trajectory reduces the buffer size requirements at each node as well as the delay between successive visits.

In recent years, a number of papers have shown that the scheduled traffic model, which exploits knowledge of the connection holding times of traffic demands, can lead to significant improvements in resource utilization in WDM networks. In such a traffic model, the setup and the teardown times of the

A node in a wireless sensor network typically consists of a micro-controller, a communication device or transceiver, and a battery unit for powering the transceiver and other devices. An important feature of wireless sensor networks is the low power consumption requirement, since these sensor nodes carry generally irreplaceable power sources or batteries. We consider the problem of assigning a power to each node in the network such that the induced connectivity graph is strongly connected with only bidirectional links, and the sum total of powers assigned to all sensor nodes is minimized. This will allow the nodes to communicate with each other, while conserving battery power as much as possible. This problem has been shown to be strongly NP-complete and heuristic approaches for solving this problem have been reported in the literature. In this paper, we establish a lower bound on the optimal power value, and provide a sufficient condition for a minimal spanning tree (MST) based approach to be an optimal solution to the problem. Based on this condition, we propose a novel heuristic approach which computationally outperforms previously reported heuristics.

Two-tiered sensor networks, where higher-powered relay nodes are used as cluster heads, have been proposed recently for designing sensor networks. Assigning sensor nodes to clusters, in an energy efficient way, is known to improve the lifetime of such networks. In this paper we have proposed an efficient distributed algorithm for assigning sensor nodes to clusters in two-tiered networks, using both single-hop and multi- hop routing schemes. Our distributed clustering strategy allocates sensor nodes to clusters, based on limited local information only. However, the solutions generated are shown to be comparable to optimal solutions obtained using an ILP formulation. We have also compared our approach to a number of existing heuristics recently proposed in the literature and have shown, through simulations, that our approach consistently outperforms current heuristics. In summary, the quality of the solutions obtained using our approach is comparable to those obtained using an ILP formulation, but the solutions can be generated very quickly, making it suitable for practical-sized networks with hundreds of sensor nodes.

Higher-powered relay nodes have been proposed as cluster heads in hierarchical sensor networks to increase the network connectivity, coverage and lifetime. Determining an appropriate placement scheme of the relay nodes that ensures adequate coverage and connectivity, while using a minimum number of relay nodes, is an important design problem and a significant amount of work has been done in this area in recent years. However, most of the existing placement strategies typically assume only stationary nodes, where data of each relay nodes (received from the underlying sensor nodes in its cluster) are routed to the base station(s), using either single-hop or multi-hop routing schemes. Recently, the use of mobile data collectors (MDC) has been shown to improve the network performance in a variety of sensor network applications. In this paper, we consider a hierarchical relay node based network, where a mobile data collector moves along a fixed trajectory, collects data from each relay node and delivers them to the base station. Such a model reduces the energy dissipation of the relay nodes by relieving them of the burden of transmitting data over longer distances, thereby increasing the overall lifetime of the network. The issue is to find the minimum number of relay nodes, along with their locations such that all network requirements are satisfied. We present an integrated integer linear program (ILP) formulation that takes into consideration the sensor data rates, the relay nodes buffer size and the speed of the MDC, and determines an optimal relay node placement scheme, which ensures that there is no data loss due to relay node buffer overflow and the energy dissipation does not exceed a specified level.

Abstract In hierarchical sensor networks using relay nodes, sensor nodes are arranged in clusters and higher poweredrelay nodescan be used as cluster heads. The lifetime of such a network is determined primarily by the lifetime of the relay nodes. In this paper, we propose two new integer linear programs (ILPs) formulations for optimal data gathering, which maximize the lifetime of the upper tier relay node network. Unlike most previous approaches considered in the literature, our formulations can generate optimal solutions under thenon‐flow‐splitting model. Experimental results demonstrate that our approach can significantly extend network lifetime, compared to traditional routing schemes, for the non‐flow‐splitting model. The lifetime can be further enhanced by periodic updates of the routing strategy based on the residual energy at each relay node. The proposed rescheduling scheme can be used to handle single or multiple relay node failures. We have also presented a very simple and straightforward algorithm for the placement of relay nodes. The placement algorithm guarantees that all the sensor nodes can communicate with at least one relay node and that the relay node network is at least 2‐connected. This means that failure of a single relay node will not disconnect the network, and data may be routed around the failed node. The worst case performance of the placement algorithm is bounded by a constant with respect to any optimum placement algorithm. Copyright © 2008 John Wiley & Sons, Ltd.

There has been considerable research interest in the design of survivable grooming capable networks in recent years. For such networks, protection may take place at the lightpath level or at the connection level. The vast majority of the current work can be classified into one of two categories (i) static grooming, where the demands are allocated for the entire duration of the network and (ii) dynamic grooming, where the start times and durations of demands are generated randomly based on certain traffic distributions. In this paper, we propose a new technique for survivable traffic grooming under the scheduled traffic model that exploits knowledge of the connection holding times of traffic demands to lead to more efficient resource allocation. We present efficient integer linear program (ILP) formulations for the complete survivable traffic grooming problem in WDM networks. Our formulations can solve the joint problem of the topology design, traffic routing and RWA, using path protection at lightpath level. Our aim is to design a stable logical topology that can accommodate a collection of low-speed traffic demands with specified setup and teardown times. The objective function, considered in our ILP formulation, is to minimize the resource requirements. This can be easily modified to maximize the throughput under a given set of resources. We also have proposed a simplified version of our ILP formulations that can solve the problem in a way that is computationally more efficient. To the best of our knowledge, this is the first paper to address the survivable traffic grooming problem under the scheduled traffic model.

Component failure in a WDM network is a serious problem that has attracted considerable attention in recent times. In a standard protection (or restoration) scheme the objective is to preserve the logical topology by switching over to back-up paths (or by setting up new lightpaths) after a fault occurs. In this paper we have proposed a new scheme where we handle a fault simply by modifying the traffic routing scheme to avoid the fault. We show that it is possible to guarantee that a significantly high number of requests for communication can be handled using this scheme, irrespective of the location of the fault. Two new integer linear program formulations have been presented using this approach. The first formulation assumes a fixed RWA, while the second finds the optimal RWA for maximizing guaranteed throughput. A large number simulation experiments demonstrate that, in the vast majority of cases, an optimal solution obtained using our second formulation not only generates a survivable routing but handles all the requests that the original fault-free logical topology was designed to handle.

Traffic grooming techniques in optical networks are attracting increasing research attention in order to handle the huge bandwidth mismatch between high capacity lightpaths and low-rate individual traffic requests. It is important to have guaranteed survivability of all user connections in such networks. Path protection has emerged as a widely accepted technique for survivable WDM network design. However, it requires allocating resources for backup lightpaths, which remain idle under normal fault-free conditions. In this paper, we introduce a new design strategy for survivable traffic grooming in WDM networks, under specified resource constraints. Our approach addresses the complete design problem including logical topology design, RWA, and routing of (subwavelength) requests over the logical topology. We further ensure that the resultant logical topology is able to handle the entire traffic request after any single link failure. We first present two ILP formulations for optimally designing a survivable logical topology, and then propose a heuristic for larger networks. Experimental results demonstrate that this new approach is able to provide guaranteed bandwidth, and is much more efficient in terms of resource utilization, compared to both dedicated and shared path protection.

Two-tiered sensor networks have gained popularity in recent years, due to their ability to facilitate load-balanced data gathering, fault-tolerance as well as increased network connectivity and coverage. Using higher-powered relay nodes as cluster heads can lead to further improvements in network performance. It is important to determine an appropriate placement scheme for such relay nodes, in order to achieve specified coverage and connectivity requirements with as few relay nodes as possible. A significant amount of work has been done in this area in recent years. However, existing placement strategies typically do not consider energy dissipation due to routing and are not capable of optimizing the routing scheme and placement concurrently. In this paper, we propose an integrated integer linear program (ILP) formulation that determines the minimum number of relay nodes, along with their locations and a suitable communication strategy such that i) all sensor nodes are able to connect to at least ksrelay nodes, ii) the upper tier relay node network is at least Kr-connected and iii) the network has a guaranteed lifetime. We also present an intersection based scheme for creating the initial set of potential relay node positions, which are used by our ILP, and evaluate its performance under different conditions. Experimental results on networks with hundreds of sensor nodes show that our approach leads to significant improvements over existing energy-unaware placement schemes.

It has been shown that for the scheduled traffic model, connection holding time aware algorithms lead to more efficient resource allocation. The setup and teardown times of the scheduled demands may be fixed, or may be allowed to slide within a larger window. A number of optimal integer linear program (ILP) solutions for the first problem (fixed setup/teardown times) have been presented in the literature, for wavelength convertible networks. In this paper we present a new and complete ILP formulation for both fixed window model, and the more general sliding scheduled traffic model, where the setup and teardown times may vary within a specified range. We consider fault-free as well as survivable networks using path protection, and do not require any wavelength conversion. Our ILP can jointly optimize the problem of scheduling the demands (in time) and allocating resources for the scheduled lightpaths. We have shown that the complexity of our formulation for sliding scheduled traffic model, in terms of the number of integer variables, is less than existing ILP formulations for the simpler fixed window model. For very large networks, we have proposed a fast two-step optimization process. The first step schedules the demands optimally in time, such that the amount of overlap is minimized. The second step uses a connection holding time aware heuristic to perform routing and wavelength assignment for the scheduled demands.

Traffic grooming techniques are used to combine low-speed data streams onto high-speed lightpaths with the objective of minimizing the network cost, or maximizing the network throughput. In this paper, we first present an efficient integer linear program (ILP) formulation for traffic grooming on mesh WDM networks. Our formulation can be easily modified to implement different objective functions. Unlike previous formulations, our ILP formulation can be used for practical sized networks with several hundred requests. We then propose a second ILP for traffic grooming, with the simplifying assumption that RWA is not an issue. This second formulation is able to generate, in a reasonable time, grooming strategies, for networks with over 30 nodes, with hundreds and even thousands of low-speed data streams. Finally, we introduce a set of ILP formulations for traffic grooming, where the logical topology is specified. We have studied, using simulation, the time needed to determine grooming strategies, using the different ILP formulations.

Nodes in sensor networks are often prone to failure, particularly when deployed in hostile territories, where chances of damage/destruction are significantly higher. There is also the possibility for the loss of connectivity between nodes due to the inherent limitations of the wireless communication medium. Therefore, a sensor network should be designed in such a way that the network is able to continue to operate, even if some of the nodes/links in the network fail. The scalability and the lifetime of sensor networks are affected by the limited transmission range and the battery power of sensor nodes. Recently, relay nodes have been proposed for balanced data gathering, reduction of transmission range, connectivity and fault tolerance. In hierarchical sensor networks using relay nodes, sensor nodes are arranged in clusters and higher-powered relay nodes can be used as cluster heads. Finding the minimum number of such relay nodes, along with their locations, so that each sensor node can communicate with at least ks(ks= 1,2...) relay nodes and the relay node network is kr-connected (kr= 1,2...), is known to be a difficult problem. Some recent works in this area have proposed heuristic solutions for the the special cases of ks= 1 or 2 and kr= 1 or 2. In this paper, we have presented a generalized integer linear program (ILP) formulation capable of generating exact solutions for arbitrary values of ksand kr.

In hierarchical sensor networks, sensor nodes are arranged in clusters, and higher-powered relay nodes can be used as cluster heads. The scalability and the lifetime of sensor networks are affected by the limited transmission range and battery power of the nodes. Proper techniques for assigning sensor nodes to clusters have been shown to improve the lifetime of the network. Previous approaches to clustering focus on different heuristics to achieve load balancing. In this paper, we have proposed two fast and efficient integer linear program (ILP) formulations for assigning sensor nodes to clusters in a two-tiered network, where the relay nodes are used as cluster heads. The first is for single hop routing and the second is a generalized formulation that can be used with any multi-hop routing strategy. The objective, in both cases, is to maximize the lifetime of the relay node network. We have tested our formulations with a number of different routing strategies, and for each case, we have compared our formulation to several existing heuristics for clustering. The results demonstrate that our ILP's consistently outperform the heuristics and are fast enough to be used for practical networks with hundreds of sensor nodes.

The deployment of multifiber, wavelength division multiplexing (WDM) networks can offer significant economic benefits over single fiber networks, because of their ability to relax the restrictions due to the wavelength continuity constraint and the potential to handle future growth. In this paper we introduce a new integer linear program (ILP) formulation for dynamic wavelength allocation in survivable, multifiber WDM networks. Single fiber networks, both with and without wavelength conversion, can be treated as a special case of our formulation. We have tested our formulations on several well- known WDM networks and compared the results to single fiber networks. We have also proposed a simple heuristic for dynamic lightpath allocation. Experimental results demonstrate our ILP formulation is feasible for current networks under low to medium traffic. For very large or highly congested networks, the heuristic can be used.

In the scheduled traffic model, the design problem is to allocate resources to a set of demands whose setup and teardown times are known in advance. A number of integer linear program (ILP) solutions for this problem have been presented in the literature. In this paper we present a new ILP formulation for routing and wavelength allocation, under the scheduled traffic model that minimizes the congestion of the network. We propose two levels of service, where idle backup resources can be used to carry low priority traffic, under fault-free conditions. When a fault occurs, and resources for a backup path need to be reclaimed, any low priority traffic on the affected channels is dropped. The results demonstrate that this can lead to significant improvements over single service level models. We are able to generate optimal solutions for moderate sized networks, within a reasonable amount of time. Finally, we present a simple and fast heuristic that can quickly generate good solutions for much larger networks.

In the scheduled traffic model, the design problem is to allocate resources to a set of demands whose setup and teardown times are known in advance. The setup and teardown times may be fixed, or may be allowed to slide within a larger window. Optimal integer linear program (ILP) solutions for the first problem (fixed setup/teardown times) have been presented in the literature. In this paper we present a new and complete ILP formulation for the more general flexible window scheduled traffic model, where the setup and teardown times may vary within a specified range. We consider a survivable, wavelength convertible network, using path protection techniques. Our ILP provides an integrated solution, which jointly optimizes the problem of scheduling the demands (in time) and allocating resources for the primary and backup lightpaths. We are able to generate optimal solutions, in a reasonable amount of time, for practical networks. For very large networks, we have proposed a two-step optimization process. The first step schedules the demands optimally in time, and the second step uses existing techniques for the fixed window model to perform routing and wavelength assignment for the scheduled demands.

Survivable routing of a logical topology ensures that the lightpaths are routed in such a way that a single link failure does not disconnect the network. However, even if the network remains connected after a failure, there is no guarantee that the resulting logical topology will be able to support the required traffic. In this paper, we introduce a new approach that integrates the logical topology design and survivable routing problems. When a topology is generated using our approach, it is guaranteed to have a survivable routing. We further ensure that the topology is able to handle the entire traffic demand, for any single link failure. We have formulated an ILP that optimally designs a survivable logical topology, and also proposed a fast heuristic which can be used for large networks.

In a dynamic lightpath allocation scheme, a lightpath is established on-demand, in response to a request for communication. The optimization techniques traditionally used in determining an optimum routing and wavelength assignment (RWA) in a robust WDM network are quite complex, requiring a significant amount of time. In this paper we introduce a new integer linear program (ILP) formulation for dynamic wavelength allocation in survivable, wavelength convertible WDM networks, using dedicated and shared protection. We also propose a simple and efficient heuristic. Networks with no wavelength conversion can be viewed as a special case of the heuristic. The ILPs are suitable for small to moderate sized networks. They have also been used to validate the performance of the heuristic, by comparing its results to optimal solutions generated by the ILPs. For very large or highly congested networks, the heuristic can be used

One major objective in WDM network design is to develop a logical topology and a routing that minimizes the congestion of the network. A standard approach is to decouple the problem of logical topology design and the problem of routing on this logical topology. Heuristics for finding the logical topology exist and a straight-forward linear program (LP), based on the node-arc formulation is normally used to solve the routing problem over a given logical topology. We have found that such LP formulations become computationally intractable for large networks. In this paper, we have introduced a novel approach for routing traffic over a given logical topology, using the concept of approximation algorithms. This technique allows us to efficiently route traffic for practical sized networks and obtain solutions, which are guaranteed to be within a specified bound of the optimal solution. Simulation results from different networks demonstrate that approximation algorithms can be used to quickly generate "near-optimal" solutions to the traffic routing problem in WDM networks.

This paper introduces a new and efficient mixed-integer linear program (MILP) formulation for dynamic lightpath allocation in survivable WDM networks, using both shared and dedicated path protection. The objective is to minimize the amount of additional optical resources (wavelength-links) needed for the new connection. The formulation can handle multiple levels of service and traditional shared and dedicated path protection schemes can be treated simply as a special case of the formulation. Experiments carried out on a number of different networks demonstrate that this approach can improve performance and is feasible for practical sized networks.

Commercially available fiber-optic cables allow limited numbers of wavelengths on a single fiber. In this paper we have developed a pragmatic method of implementing all-optical wavelength routed networks using bundles of fibers to realize each communication link. We have explored some interesting features of this approach for dynamic lightpath assignment. We have shown that our approach allows virtual wavelength translation where we may derive some benefits of partial wavelength translation without actually having to change the carrier frequency. This design also allows us to have bundles of varying sizes to accommodate anticipated differences in traffic through different communication links of the network. Finally, we have presented a simple dynamic scheme, based on local information alone, for allocating lightpaths.

It is desirable to have low diameter logical topologies for multihop lightwave networks. Researchers have investigated regular topologies for such networks. Only a few of these (e.g., GEMNET) are scalable to allow the addition of new nodes to an existing network. Adding new nodes to such networks requires a major change in routing scheme. For example, in a multistar implementation a large number of retuning of transmitters and receivers anti/or renumbering nodes are needed for GEMNET. We present a scalable logical topology which is not regular but it has a low diameter. This topology is interesting since it allows the network to be expanded indefinitely and new nodes can be added with a relatively small change to the network. We present the new topology, an algorithm to add nodes to the network and two routing schemes.