The adoption of Commercial Off-The-Shelf (COTS) ICs in modern satellites faces challenges from radiation-induced latchup events, with current protection methods showing significant limitations in detection accuracy and applicability. This demonstration presents a novel adaptive AI-based latchup detection and protection system featuring two-stage training and LSTM neural network analysis. Our FPGA implementation achieves 90% detection accuracy without extensive pre-characterization. Visitors can validate the system's performance through real-time interaction with various latchup scenarios.

In our envisioned ‘Next Paradigm’ of ‘New Space’, commercial-off-the-shelf (COTS) systems (embodying multiple COTS ICs) would be employed as payloads in space missions. Most COTS ICs are susceptible to radiation effects, particularly Micro-Single-Event-Latchups (μ-SELs) and SELs, and their characteristics are expectedly different. Consequently, hitherto reported detection approaches require characterization of the individual COTS ICs and the entire system, thereby rendering excessive overheads when applied to different COTS systems. In this paper, we propose, for the first time, the design and implementation of an adaptive AI-based approach to detect and protect various uncharacterized COTS systems (vis-à-vis pre-characterized ones) against μ-SELs and SELs. Our proposal involves the adoption of the Long-Short-Term-Memory (LSTM) neural network with our proposed two-stage training process – ex-situ pre-training and in-situ re-training – to improve general applicability. Our FPGA-based prototype achieves high (~90%) average accuracy for four different payloads. This is a worthy improvement of 13.3%-28.5% over reported approaches, yet requiring low (~115 mW) power consumption. Collectively, our proposed approach is appropriate for resource-constrained space applications and our ‘Next Paradigm’ of ‘New Space’.

The impending 6G communication based on the software defined radio (SDR) requires a radio frequency (RF) track-and-hold amplifier (THA). This THA serves as the frequency down-converter and the single-to-differential interface to the downstream analog-to-digital converter (ADC). We present a CMOS RF THA that features wide and width (18 GHz), yet high linearity (spurious free dynamic range (SFDR) of 56.7 dB) and not requiring an external balun. These features are derived from our proposed isolation technique based on our proposed double source follower enhanced (DSFE) structure. To realize the single-to-differential conversion without an external balun, we design an independent balun as the first stage. Thereafter, we employ our proposed feedforward compensation technique (FCT) along with the reported phase correction technique (PCT) to reduce the output mismatches while simultaneously enhancing the linearity and bandwidth. We monolithically realize the RF THA in 22-nm fully-depleted silicon-on-insulator (FD-SOI) CMOS operating at 1.8 V. Measurements depict that the input bandwidth is wide (18 GHz), yet featuring high linearity (SFDR =56.7 dB at 15 GHz) with 2 GS/s sampling rate. The power consumption and the chip area are low and small at 216 mW and 0.07 mm2, respectively. When benchmarked against reported III/V RF THAs, the proposed CMOS RF THA is very competitive—comparable bandwidth, yet simultaneously higher linearity, potentially lower cost, lower power dissipation, and smaller die area. Further because it is realized in CMOS, it facilitates integration to other CMOS circuits in the same system-on-chip (SoC).

In order to overcome the problems of low channel utilization, low transmission success rate and high data transmission delay in current gateway node reconfiguration methods of IOT, this paper proposes a novel gateway node reconfiguration method of IOT based on hierarchical coding particle swarm optimization. Based on the IOT network model, this paper analyzes the delay characteristics of the IOT, and constructs the object function of the gateway node reconfiguration of IOT. By monotone decreasing inertia weight strategy, the coding particle swarm optimization is optimized, and the reconfiguration objective function of the gateway node of IOT by using the optimized particle swarm optimization algorithm is solved. Experimental results show that the channel utilization ratio of the proposed method is higher than 90%, the success rate of information transmission is more than 80%, and the data transmission delay is less than 0.5 s, which indicates that the proposed method has high channel utilization, high transmission success rate and low data transmission delay.

Advanced satellites and/or high-level (levels 4 and 5) autonomous vehicles demand high reliability integrated circuits (ICs) with ultra-low error rates. One solution is to use radiation-hardened-by-design (RHBD) design techniques to mitigate the error rates against the single-event-effects (arising from radiation effects). This paper first provides an overview on several present-art RHBD design techniques, and then propose an RHBD design methodology, spanning from the library cell development, circuit simulation and synthesis, to the layout implementation, to realize digital circuits. We further demonstrate an 8051 microcontroller with the proposed design methodology, and evaluate the 8051 microcontroller prototype (@ 65nm CMOS) with irradiation tests. Our 8051 microcontroller is error-free with 10 MeV.mg/cm2, meeting our targeted specifications for Low Earth Orbit applications. When under high Linear Transfer Energy (> 51.5 MeV.mg/cm2) tests, the 8051 microcontroller does suffer errors. We further study/analyze which part of the 8051 microcontroller to cause errors, and provide recommendations.

Public vehicle service (PVS), as a paradigm to manage and share large-capacity vehicles for public passenger delivery, is promising to improve the quality of urban transportation. In the PVS system, a command center receives requests sent by passengers, periodically assigns them to public vehicles and schedules vehicle routes to serve the requests. However, in the PVS system, the passengers' waiting time is not well utilized. Moreover, it is observed that the driving distance on low-speed roads accounts for a rather high percentage. These two factors impact on system efficiency. In order to utilize the waiting time, we propose to let passengers walk a short distance instead of standing at their origins. At the same time, the driving distance on low-speed roads will be reduced. In this paper, the closest meeting point algorithm is proposed to address the challenge of determining the best pick-up and drop-off locations. The large-scale simulations show that the passenger walking and the proposed fast-route scheduling strategy can shorten the total vehicle travel distance by 34%.

We present a low gate-count ultra-small area nano advanced encryption standard (AES) design. We achieve the low gate-count by the following means. First, we repeatedly reuse the area-critical circuits, i.e. one 8-bit Substitute-Box (S-Box) circuit and one 32-bit MixColumn circuit, for AES. Second, we cascade the input flip-flops (FFs) with our data transfer architecture so that the outputs of the MixColumn circuit are connected directly to the first 32-bit input FFs without extra multiplexing circuits. Third, the ShiftRow operation is implicitly performed by assigning the data sequence to the input FFs (during the S-Box and MixColumn operations). Fourth, we use independent XOR gates for AddRound and KeyExpansion operations. The collective means enables our design to feature 1457 gates, and to occupy 100um×100um area @ 65nm CMOS. When compared to the normalized area (@ 65nm CMOS) of the reported AES designs, our design features the smallest normalized area, 10% smaller than the most competitive reported AES design. Our design is targeted for ultra-small area applications including biomedical applications.

This paper presents a high-switching-frequency and high-efficiency dual-phase output stage for Point-of-Load (POL) converters. The proposed design is based on a novel air-core coupled-inductor that exhibits variable inductance. Specifically, the proposed coupled-inductor exhibits different equivalent inductance within one switching cycle, thus offering combined merits of fast transient response, small current ripple, and good current balance. The prototype output stage, realized in a 180nm CMOS process, operates up to 30MHz and features the input voltage range of 1.8-3.6V and the output voltage range of 0.6-3.3V. A maximum output power of 6.6W and a peak power efficiency of 88.0% are achieved. Further, in comparison with the conventional approaches, the proposed dual-phase output stage achieves 13% smaller current ripple and 54% faster transient response.

Chip multiprocessors (CMPs) involve directory storage overhead if cache coherence is realized via sharer tracking. This work proposes a novel framework dubbed non-uniform directory architecture (NUDA), by leveraging our two insights in that the number of “active” directory entries required to stay on chip is usually small for a short execution time window due to high directory locality, and that the fraction of interrogated directory entries drops as the core count rises. Unlike earlier storage overhead reduction techniques that require all cached LLC blocks to have their directory entries fully on chip, NUDA dynamically buffers only most active directory vectors (DVs) on chip while keeping DVs of all LLC blocks in a backing store at low level storage. NUDA attains its superior efficiency via an inventive criticality-aware replacement policy (CARP) for on-chip buffer management and effective prefetching to pre-activate vectors (PAVE) for upcoming coherence interrogations. We have evaluated NUDA by gem5 simulation for 64-core CMPs under PARSEC and SPLASH benchmarks, demonstrating that CARP and PAVE enhance on-chip directory storage efficiency significantly. NUDA with a small on-chip buffer for DVs exhibits negligible performance degradation (to stay within 2.6 percent) compared to a full on-chip directory, while outperforming its previous counterparts for directory area reduction when on-chip directory budget is provisioned scarcely for high scalability.

To lower on-chip SRAM area overhead for chip multiprocessors (CMPs), this work treats a novel directory design which compresses present-bit vectors (PVs) by dropping “runs of zeros” commonly existing and lets PVs be transformed to their variations after sharer relinquishment for hashing alternative table sets to lift table utilization. Featured with relinquishment coherence and compressed sharer tracking (ReCoST), the proposed design attains superior directory efficiency and maintains “exact” directory representations, as a result of dropping abound long runs of zeros present in PVs. According to full-system simulation using gem5 for a range of core counts under PARSEC benchmarks, ReCoST is found to enjoy 3.21χ (or 2.64χ) more efficiency in directory storage than conventional bit-tracking directories (or the best directory known so far, called SCD) for a 64-core CMP under monotasking (or multitasking) workloads while ensuring execution slowdowns to stay within 2.4 percent (or 3.3 percent).

We present a single-channel 10-b 400-MS/s successive approximation register (SAR) analog-to-digital converter (ADC) embodying a proposed 2-b/step conversion scheme with single reference voltage for the IEEE 802.11ac. By means of the said scheme, the proposed ADC requires only three capacitor arrays instead of at least four capacitor arrays in other capacitor digital-to-analog converter-based 2-b/step SAR ADCs. The proposed ADC features a small input capacitance loading, thereby alleviating the driving requirement of the power-hungry input buffer in the IEEE 802.11ac system; and features a symmetrical architecture with highly matched interconnections. In addition, the proposed ADC embodies a proposed high-speed dynamic comparator with kickback noise cancelation and high-speed successive approximation (SA) control logic for high conversion rate and resolution. The proposed ADC prototype fabricated in 65-nm CMOS process achieves signal-to-noise-and-distortion-ratio >52 dB across 200-MHz Nyquist bandwidth, while dissipating 5.61-mW power. The ADC prototype, when benchmarked with state-of-the-art 2-b/step SAR ADCs, features a highly competitive figure-of-merit, i.e., 43 fJ/conv.step.

A directory-based chip multiprocessor (CMP) suffers from excessive directory area overhead when its size grows. This work leverages novel relinquishment coherence and superior directory efficiency (RECODE) to lower area overhead. Relinquishment coherence boosts the utilization of a hash-based, set-associative table which holds distinct present-bit vectors (PVs), as it transforms a conflict PV to its variations after sharer relinquishment for hashing alternative sets. Superior directory efficiency is resulted from both boosted table utilization and table width shrunk via dropping “runs of zeros” commonly found in PVs. RECODE Table utilization is elevated by relinquishment coherence, which transforms a conflict PV to its variations after sharer relinquishment for hashing alternative sets. RECODE maintains “exact” directory representations for simple coherent logics and low coherent traffic. RECODE is found to enjoy 3.21× more storage efficiency than conventional bit-tracking directories for a CMP with 64 cores and it is 2.64× more storage efficient than the best directory SCD known so far.

Although Total Ionizing Dose (TID) effects are generally unpronounced in deep-submicron-CMOS, we show the TID-induced leakage current @TID=500Krad is significant in NMOS-finger-transistors of GlobalFoundries 65nm CMOS. Further, Radiation-Hardening-By-Design techniques against said TID effect are recommended.

We comprehensively study three types of radiation-hardened flip-flops: DICE for SEU-hardening, temporal for SET-hardening, and Triple-Modular-Redundancy for SEU-cum-SET-hardening. Our study includes their trade-offs of circuit/radiation-hardness attributes. We find that DICE flip-flops remain the most competitive.

Public vehicle (PV) systems will be efficient traffic-management platforms in future smart cities, where PVs provide ridesharing trips with balanced QoS (quality of service). PV systems differ from traditional ridesharing due to that the paths and scheduling tasks are calculated by a server according to passengers' requests, and all PVs corporate with each other to achieve higher transportation efficiency. Path planning is the primary problem. The current path planning strategies become inefficient especially for traffic big data in cities of large population and urban area. To ensure real-time scheduling, we propose one efficient path planning strategy with balanced QoS (e.g., waiting time, detour) by restricting search area for each PV, so that a large number of computation is saved. Simulation results based on the Shanghai (China) urban road network show that, the computation can be reduced by 34% compared with the exhaustive search method since many requests violating QoS are excluded.

In Intelligent Transport field, the Public Vehicle System is proposed to introduce a concept of a specialized vehicle for public transportation, which can integrate and substitute for vehicles such as taxis, buses and railways. Public Vehicle model has several advantages over earlier models, but the algorithm proposed in the model can't consider all potential solutions when building new paths, resulting in a decrease in performance. We expand the searching method to cover all cases of insertion and achieve a lower cost. Our simulations show that the Combinatorial Insertion Algorithm can have a 5%-11% promotion in total traveling distance.

The increasing number of vehicles nowadays makes it hard to manage traffic flow on the streets, especially when it comes to intersection management. This paper proposes the use of dashboard traffic lights (DTL), an intelligent traffic light system based on client-server communication that will use V2I (Vehicle-to- Intersection) network scheme to send request messages from moving vehicles to the intersection station that will analyze the request message and send back the decision message based on the intersection status. The average waiting time and the number of vehicles stopping at the intersection is significantly reduced.

The proliferation of smartphones has enabled a novel paradigm, participatory sensing, which leverages the smartphones to collect and share data about their surrounding environment. Since the sensing tasks are location-dependent and have time features, it is crucial and challenging to find a proper allocation of sensing tasks to ensure the timeliness of tasks and the quality of sensing data. In this paper, we investigate the heterogeneous sensing task allocation problem aiming at minimizing the total penalty caused by the tardiness of tasks. We prove this problem is NP-hard and propose two hybrid algorithms which combine a heuristic algorithm and two meta-heuristic algorithms respectively. The extensive simulation results show that the proposed hybrid algorithms outperform the meta-heuristic algorithms.

Substantial technology advances have been made in areas of autonomous and connected vehicles, which opens a wide landscape for future transportation systems. We propose a new type of transportation system, Public Vehicle (PV) system, to provide effective, comfortable, and convenient service. The PV system is to improve the efficiency of current transportation systems, \eg, taxi system. Meanwhile, the design of such a system targets on significant reduction in energy consumption, traffic congestion, and provides solutions with affordable cost. The key issue of implementing an effective PV system is to design efficient scheduling algorithms. We formulate it as the PV Path (PVP) problem, and prove it is NP-Complete. Then we introduce a real time approach, which is based on solutions of the Traveling Salesman Problem (TSP) and it can serve people efficiently with lower costs. Our results show that to achieve the same performance (e.g., the total time: waiting and travel time), the number of vehicles can be reduced by 47%-69%, compared with taxis. The number of vehicles on roads is reduced, thus traffic congestion is relieved.

Subthreshold voltage references are increasingly prevalent in power-critical applications due to their low-voltage and ultra-low-power attributes. However, the effective temperature range of state-of-the-art subthreshold voltage references remains undesirably narrow for low temperature coefficient (TC) operation and/or their PSRR is low - thereby severely limiting their range of applications. In this paper, we present a novel subthreshold voltage reference embodying a novel paralleled `2-Transistor' structure and a novel auxiliary amplifier. The former serves to facilitate low TC within a wide temperature range, and the latter for high PSRR and low line-sensitivity. The proposed design achieves low TC of 17ppm/°C within a wide effective temperature range of -40°C to 125°C, and high PSRR of 75dB and low line-sensitivity of 0.3%/V with minimum 0.5V supply voltage and 32nW power consumption. Both the TC and PSRR parameters are, at this juncture, the best performance compared to reported subthreshold voltage references, but with a slight power penalty.

Fingerprinting based localization is one of the most widely used indoor localization methods. This method is divided into two phases: during the off-line training phase, fingerprints within the area of interest are collected and stored in a fingerprint database; during the on-line mapping phase, the real-time location of a device is estimated by mapping itself to the most accurate fingerprint in the database. The efficiency of the mapping process is one of the key challenges of the on-line phase, and is mostly characterized by the localization accuracy and the response time. Clustering methods have been introduced to reduce computational overhead. In this paper, we propose a dynamic clustering method leveraging the inertial information of the target device. An active area is dynamically computed around the prior position. The target mapping space is significantly reduced with this active area. This method can be integrated with other clustering algorithms to overcome the edge problem and remove outliers. We evaluate this method compared with the state-of-the-art methods on a body sensor based localization system. The results show that the accuracy, precision and response time of the system are improved greatly.

The increasing number of vehicles nowadays makes it hard to manage traffic flow on the streets, especially when it comes to intersection management. This paper proposes the use of dashboard traffic lights (DTL), an intelligent traffic light system based on client-server communication that will give each vehicle a decision based on the speed and direction of the vehicle. This system can be used for both human controlled vehicles and autonomous cars. The average waiting time for all vehicles and the number of cars stopping at the intersection is significantly reduced. The intersection throughput is increased.

A modern general-purpose graphics processing unit (GPGPU) usually consists of multiple streaming multiprocessors (SMs), each having a pipeline that incorporates a group of threads executing a common instruction flow. Although SMs are designed to work independently, we observe that they tend to exhibit very similar behavior for many workloads. If multiple SMs can be grouped and work in the lock-step manner, it is possible to save energy by sharing the front-end units among multiple SMs, including the instruction fetch, decode, and schedule components. However, such sharing brings architectural challenges and sometime causes performance degradation. In this article, we show our design, implementation, and evaluation for such an architecture, which we call Buddy SM . Specifically, multiple SMs can be opportunistically grouped into a buddy cluster. One SM becomes the master, and the rest become the slaves. The front-end unit of the master works actively for itself as well as for the slaves, whereas the front-end logics of the slaves are power gated. For efficient flow control and program correctness, the proposed architecture can identify unfavorable conditions and ungroup the buddy cluster when necessary. We analyze various techniques to improve the performance and energy efficiency of Buddy SM. Detailed experiments manifest that 37.2% front-end and 7.5% total GPU energy reduction can be achieved.

Electric vehicle (EV) is a promising transportation with plenty of advantages, e.g., low carbon emission, high energy efficiency. However, it requires frequent and long time charging. In public charging stations, EVs spend long time on queuing especially during peak hours. Hence, it requires an efficient method to reduce the total charging time for EVs. We study the Electric Vehicle Charging-Scheduling (EVCS) problem in this paper. First we prove that EVCS is NP-Complete, which can be reduced from one Parallel Machine Scheduling (PMS) problem. Then two heuristic algorithms are proposed: the Earliest Start Time (EST) algorithm, and the Earliest Finish Time (EFT) algorithm. EST tries to advance the start charging time to get customers in service as early as possible, while EFT focuses on the possible finish charging time to get customers served as soon as possible. Finally simulations show that, the proposed algorithms outperform the classic greedy nearest scheduling algorithm: assign each EV to its nearest charging station, then choose the outlet where the fewest EVs are queuing. Typically, under our simulation settings, the average finish time and maximum finish time can be reduced by about one hour, and six hours respectively.

Coverage is a fundamental problem in wireless sensor networks (WSNs). Conventional studies on this topic focus on 2D ideal plane coverage and 3D full space coverage. The 3D surface of a field of interest (FoI) is complex in many real-world applications. However, existing coverage studies do not produce practical results. In this paper, we propose a new coverage model called surface coverage. In surface coverage, the field of interest is a complex surface in 3D space and sensors can be deployed only on the surface. We show that existing 2D plane coverage is merely a special case of surface coverage. Simulations point out that existing sensor deployment schemes for a 2D plane cannot be directly applied to surface coverage cases. Thus, we target two problems assuming cases of surface coverage to be true. One, under stochastic deployment, what is the expected coverage ratio when a number of sensors are adopted? Two, if sensor deployment can be planned, what is the optimal deployment strategy with guaranteed full coverage with the least number of sensors? We show that the latter problem is NP-complete and propose three approximation algorithms. We further prove that these algorithms have a provable approximation ratio. We also conduct extensive simulations to evaluate the performance of the proposed algorithms.

In wireless sensor networks (WSNs), since many basic scientific works heavily rely on the complete sensory data, data recovery is an indispensable operation against the data loss. Several works have studied the missing value problem. However, existing solutions cannot achieve satisfactory accuracy due to special loss patterns and high loss rates in WSNs. In this work, we propose a multiple attributes-based recovery algorithm which can provide high accuracy. Firstly, based on two real datasets, the Intel Indoor project and the GreenOrbs project, we reveal that such correlations are strong, e.g., the change of temperature and light illumination usually has strong correlation. Secondly, motivated by this observation, we develop a Multi-Attribute-assistant Compressive-Sensing-based (MACS) algorithm to optimize the recovery accuracy. Finally, real trace-driven simulation is performed. The results show that MACS outperforms the existing solutions. Typically, MACS can recover all data with less than 5% error when the loss rate is less than 60%. Even when losing 85% data, all missing data can be estimated by MACS with less than 10% error.

Recent advances in wireless communication and electronic manufacture have enabled a variety of sensors to be used for Wireless Body Area Networks (WBANs), which can provide real-time body monitoring and feedback for enabling patient diagnostics procedure, rehabilitation, sports training and interactive performance. However, existing single-hop wireless communication scheme faces several major challenges: rapid growth of channel conflicts as more sensors added, impermeability of human body to radio waves and highly dynamic network topology due to human movements. In this paper, a prototype of multi-hop WBAN has been built to quantify the channel conflict and to characterise the network connectivity during human motions. A probability based routing protocol fusing inertial sensor data and history link quality is then developed, which aims at capturing the high spatio-temporal change of network topology on the selection of a reliable relay node in WBAN routing. The performance of the protocol is experimentally evaluated on our prototype system. Compared with a number of existing routings, the proposed scheme is more splendid in terms of average delivery ratio, number of hops and end-to-end delay.

An urban vehicular network is a typical type of Delay Tolerant Network (DTN). Based on the routing analysis in a DTN, we first put forward a Minimum Delay and Hop Algorithm (MDHA), which requires both historical and future information on all the vehicles in the network. Since MDHA is not practical, we then design a Traffic Aware Routing Algorithm (TARA), which uses the historical and the real-time vehicle information to make routing decisions on the road structure level. A simulation using real GPS data in Shanghai shows that TARA significantly reduces the transmission delay and the hop count compared to the traditional GEO routing and GPSR.

This paper introduces WiBEST, Wireless Body and Environmental Sensor Tracking platform, for personal indoor positioning. WiBEST is built with portable on-body sensor nodes and assisted sensor nodes deployed in the targeted indoor area. It takes a hybrid approach with pedestrian dead reckoning and radio-based localization and explore the their cooperative efforts. Real-time inertial measurements are combined with RSSI-based information, and then processed with an Extended Kalman Filter to be weighted in the location estimation according to their reliability. WiBEST also incorporates with an adaptive Step Length Algorithm to reduce the deviation of the measurements.The experimentation results show that WiBEST can improve the accuracy of the positioning by 66.3% compared to pure inertial solution. With the popularity of wearable devices with inertial sensors and wireless communication chips, we believe that this approach is very promising for personal indoor positioning services.

Data loss is ubiquitous in wireless sensor networks (WSNs) mainly due to the unreliable wireless transmission, which results in incomplete sensory data sets. However, the completeness of a data set directly determines its availability and usefulness. Thus, sensory data recovery is an indispensable operation against the data loss problem. However, existing solutions cannot achieve satisfactory accuracy due to special loss patterns and high loss rates in WSNs. In this work, we propose a novel sensory data recovery algorithm which exploits the spatial and temporal joint-sparse feature. Firstly, by mining two real datasets, namely the Intel Indoor project and the GreenOrbs project, we find that: (1) for one attribute, sensory readings at nearby nodes exhibit inter-node correlation; (2) for two attributes, sensory readings at the same node exhibit inter-attribute correlation; (3) these inter-node and inter-attribute correlations can be modeled as the spatial and temporal joint-sparse features, respectively. Secondly, motivated by these observations, we propose two Joint-Sparse Sensory Data Recovery (JSSDR) algorithms to promote the recovery accuracy. Finally, real data-based simulations show that JSSDR outperforms existing solutions. Typically, when the loss rate is less than 65%, JSSDR can estimate missing values with less than 10% error. And when the loss rate reaches as high as 80%, the missing values can be estimated by JSSDR with less than 20% error.

With recent progress in vehicle autonomous driving and vehicular communication technologies, vehicle systems are developing towards fully connected and fully autonomous systems. This paper studies lane assignment strategies for connected autonomous vehicles in a highway scenario and their impact on the overall traffic efficiency and safety. We formulate a model of connected autonomous vehicles, which includes three features: traffic data available online, ultra-short reaction time, and cooperative driving. Based on this model, we propose a novel lane change maneuver Politely Change Lane (PCL), which achieves the tradeoff between traffic safety and efficiency. Its effectiveness is validated and evaluated by extensive simulations. The performance shows that PCL improves both safety and efficiency of the overall traffic, especially with heavy traffic.

In most delay tolerant network (DTN) applications, mobile nodes utilize WiFi radios to obtain local information and transmit data. One bottleneck on DTN delivery performance is the short communication range of the WiFi radio. Rather than designing efficient protocols on WiFi based DTN, we propose a novel dual-radio architecture by adding a long-range low-bitrate eagle eye (EE) radio on every node. This EE radio can “see” real-time movement information of nodes in a significantly large range, and so much early scheduling can be done with this radio when compared with WiFi which is still in charge of data transmissions. Benefiting from this cooperative dual radios architecture, we design distributed EE routing protocol for minimizing delivery delay in DTNs. Through our prototype implementation with 7 EE devices and simulations based on real trace data of 4000 taxis in Shanghai, we show that the proposed architecture is able to achieve as low as 40% of the average delay with traditional DTNs.

This paper studies mobile barrier coverage (MBC) surrounding dynamic objects. In the real world, several dynamic objects can benefit from MBC. For example, marching troop can detect any adversary intrusion without blind spot by MBC. However, conventional works only focused on barrier coverage for static objects, which fail when the objects start to move. Issues to address these dynamic-object scenarios, we propose the problem of mobile barrier coverage for dynamic objects. The most challenge is how to effectively maintain MBC when the motion of objects are unpredictable. We propose a fully distributed algorithm for mobile sensor nodes to cooperatively move and maintain the high-quality barrier coverage. The extensive simulations based on large-scale trace data demonstrate the efficiency and efficacy of the proposed algorithm.

This paper proposes techniques for face detection and gives the implementation details for an FPGA development board. We analyze and discuss the relation between the system computation cost and selection of the image scaling factor. We give a new method to select the stop threshold for the image reduction process, which reduces the total computation by half. We also provide a color image output mode to let our system enjoy more human-oriented design. Test results show that the system achieves real-time face detection speed (100 fps) and a high face detection rate (87.2%) for an SVGA (600 × 800) video source. The low power consumption (3.5W) is another advantage over previous work.

Multi-Packet Reception (MPR) enables simultaneous receptions from different transmitters to a single receiver, which has been demonstrated to bring capacity improvement in wireless network. However, MPR does not improve the transmission capability of intermediate relay nodes in a multi-hop routing and thus these nodes may become the bottlenecks for increasing throughput despite of great reception capability. We investigate the scheduling for multi-hop routing with MPR to improve the network throughput under multiple data flows. We formulate the optimization problem under K-MPR model and analyze the performance upper bound with ideal scheduling. We propose a distributed scheduling scheme based on a k-Connected k-Dominating Set backbone to eliminate bottleneck effects on intermediate relay nodes as to enhance the network throughput. We show the effectiveness of our scheme by comparing its performance with the upper bound and node-disjoint routing.

In a target detection application, rational adversary targets that are conscious of the deployed location of sensor nodes are capable of planning a path in order to avoid being detected by sensor nodes. Probing sensor communication is one of the means that are used by adversary targets to get the necessary information. Therefore, this paper investigates how to reduce the sensor communication exposure. We introduce target bypassing routing methods applied on omnidirectional and directional sensor communication models to achieve the goal of reducing sensor communication exposure to targets. The simulation results show that our bypassing methods can decrease the possibility of communication exposure to a large extent. We also implement a prototype system with Iris motes to verify our solution.

Recent advances in the physical layer have enabled the simultaneous reception of multiple packets by a node in wireless networks. We address the throughput optimization problem in wireless networks that support multipacket reception (MPR) capability. The problem is modeled as a joint routing and scheduling problem, which is known to be NP-hard. The scheduling subproblem deals with finding the optimal schedulable sets, which are defined as subsets of links that can be scheduled or activated simultaneously. We demonstrate that any solution of the scheduling subproblem can be built with \vert E\vert + 1 or fewer schedulable sets, where \vert E\vert is the number of links of the network. This result is in contrast with previous works that stated that a solution of the scheduling subproblem is composed of an exponential number of schedulable sets. Due to the hardness of the problem, we propose a polynomial time scheme based on a combination of linear programming and approximation algorithm paradigms. We illustrate the use of the scheme to study the impact of design parameters on the performance of MPR-capable networks, including the number of transmit interfaces, the beamwidth, and the receiver range of the antennas.

We present a multi-objective optimization approach for joint throughput optimization and traffic engineering, where the routing request of traffic arrives one-by-one. We provide an Integer Linear Program (ILP) that simultaneously i) maximizes the aggregate throughput, ii) minimizes the resource consumption, and iii) minimizes the maximum link utilization. We study the impact of optimizing the three different objectives simultaneously in dynamic environments, and show that better solutions than those of mono-objective approaches can be obtained. Because of the complexity of the ILP, we also propose another ILP with reduced complexity, and study its performance and the optimality gap between it and optimal solutions.

In this article, we focus on a typical application of Cyber Physical System (CPS), i.e., vehicle route navigation. Two fundamental problems have been examined: 1) How different are various vehicle routing algorithms? 2) How valuable is real-time traffic information or historical traffic information in helping vehicle routing? Different from most previous works based on simulations, we presented performance comparisons of four routing algorithms using real GPS sensory data from 4000 taxis. It has been shown that using real-time traffic information could substantially improve the quality of vehicle path routing. This can benefit an individual driver, because through our evaluation results on realistic vehicle traces we found that the paths selected by taxi drivers are not as good as expected. More importantly, utilizing real-time information could improve global transportation efficiency in terms of dispersing/managing traffic, which plays a key role in constructing an effective vehicular CPS.

Throughput optimization and traffic engineering in Wavelength-Division Multiplexing (WDM) networks are usually treated as mono-objective optimization problems. In this paper, we provide a multi-objective Integer Linear Program (ILP) for the joint throughput optimization and traffic engineering problem. By simultaneously i) maximizing the throughput, ii) minimizing the resource consumption, and iii) balancing the traffic load, we demonstrate that better solutions than those of mono-objective approaches are obtained. We also present a distributed heuristic algorithm, which upper-bounds the per-route resource consumption and maximizes the throughput. Simulation results validate the proposed model and heuristic algorithm. Additionally, we present an ILP formulation for another well-known problem such as routing and wavelength assignment (RWA), and discuss the impact of modeling it as a multi-objective problem.

We address the minimum length scheduling problem in wireless networks, where each transmitter has a finite amount of data to deliver to a common receiver node (e.g., base station). In contrast with previous works that model wireless channels according to the Protocol or Physical model of interference, this paper studies the scheduling problem in multiple access (multi-access) networks. In this kind of network, the receiver node can decode multiple transmissions simultaneously if the transmission rates of concurrent transmitters lie inside the capacity region of the receiver node. We propose a linear programming model that minimizes the schedule length. The model incorporates the capacity region of multiple access channels into scheduling decisions, such that the sum of the transmission rates of simultaneous transmitters is maximized. Because of the high-complexity of the model, we also present a heuristic algorithm, whose performance is extensively evaluated and compared with the optimal solutions.

Delay Tolerant Network (DTN) is a kind of networks that have no fixed path between nodes due to lack of continuous network connectivity. To achieve successful communication and to improve performance in DTN is always a challenge work. Most existing works are based on designing high efficient routing protocols and have not emphasized the MAC layer as well as new technologies available in the Physical layer which may influence the performance for whole networks. In this paper, we consider utilization of Multi-packet Reception (MPR) capability in DTN in order to provide better performance. We introduce our own MPR scheduling scheme, Group Based Scheme (GBS), and compare the performance of DTN with different MPR capabilities. Our works have been evaluated by the simulation using a real vehicular network trace composed of the GPS data of more than 4,000 taxis in Shanghai urban area. The results have demonstrated various impacts of using Multi-Packet Reception (MPR) on performance in DTN. By using MPR in DTN, it outperforms the network without MPR especially when the wireless transmission range increases.

We consider distributed top-k processing problem in a mobile scenario. Specially, we focus on a real application of a bus network (N nodes), where buses are equipped with cameras for real-time security surveillance. Due to the limited number of screens (k, k<;<;N) at the traffic management center, how to select k bus nodes with most passengers to upload image data by DSRC needs to be solved. We present a novel distributed scheme BSS to handle this so-called "top-k node selection" issue in bus network, in which challenges of low time cost and high accuracy is not trivial. BSS utilizes various strategies to speed up top-k node selection facing poor network condition and application requirements. Performance evaluation is carried out on a real-trace driven simulator, which utilizes about 700 buses in Shanghai. The testing results show that BSS has an excellent performance in terms of time cost and average degree of accuracy, which shows the effectiveness of BSS scheme for real-time security surveillance.

Recent advances in the physical layer have enabled the simultaneous reception of multiple packets by a node in wireless networks. In this paper, we present a generalized model for the throughput optimization problem in multi-hop wireless networks that support multi-packet reception (MPR) capability. The model incorporates the multi-access channel, which accurately accounts for the achievable capacity of links used by simultaneous packet transmissions. The problem is modeled as a joint routing and scheduling problem. The scheduling subproblem deals with finding the optimal schedulable sets, which are defined as subsets of links that can be scheduled or activated simultaneously. We demonstrate that any solution of the scheduling subproblem can be built with |E| + 1 or fewer schedulable sets, where |E| is the number of links of the network. This result contrasts with a conjecture that states that a solution of the scheduling subproblem, in general, is composed of an exponential number of schedulable sets. Due to the hardness of the problem, we propose a polynomial time scheme based on a combination of linear programming and greedy paradigms. The scheme guarantees the operation of links at maximum aggregate capacity, where the sum of the capacity of the links is maximized and the multi-access channel is fully exploited.

Bus lane enforcement system aims to monitor illegal utilization of bus lane by non-permitted vehicles (violator). However, Road-side system leads to considerable infrastructure cost while bus mounted system has limited surveillance coverage. In this paper, we consider an interesting problem in bus mounted system: how to improve the surveillance coverage of bus mounted system without additional infrastructure cost? In other words, we attempt to identify not only the violator immediately in front of the bus, bus also the violators not close to the bus, whose number plates cannot be read directly because of sight blocking of bus mounted cameras. With utilization of communication between bus and existing cameras around intersections, we propose a novel cooperative violator identification scheme, DoubleChecking, with which violators can be sorted out from traffic flow with high accuracy. From theoretical analysis, DoubleChecking shows a good performance for violator identification, which demonstrates the effectiveness of the proposed scheme.

Coverage is a fundamental problem in Wireless Sensor Networks (WSNs). Existing studies on this topic focus on 2D ideal plane coverage and 3D full space coverage. The 3D surface of a targeted Field of Interest is complex in many real world applications; and yet, existing studies on coverage do not produce practical results. In this paper, we propose a new coverage model called surface coverage. In surface coverage, the targeted Field of Interest is a complex surface in 3D space and sensors can be deployed only on the surface. We show that existing 2D plane coverage is merely a special case of surface coverage. Simulations point out that existing sensor deployment schemes for a 2D plane cannot be directly applied to surface coverage cases. In this paper, we target two problems assuming cases of surface coverage to be true. One, under stochastic deployment, how many sensors are needed to reach a certain expected coverage ratio? Two, if sensor deployment can be planned, what is the optimal deployment strategy with guaranteed full coverage with the least number of sensors? We show that the latter problem is NP-complete and propose three approximation algorithms. We further prove that these algorithms have a provable approximation ratio. We also conduct comprehensive simulations to evaluate the performance of the proposed algorithms.

We propose a novel analog Class D Amplifier (CDA) based on self-oscillating modulation where the input of the feedback network is taken at the output of the lowpass LC filter (‘complete feedback’) as opposed to the prevalent (Pulse Width Modulation CDA) approach where the feedback input is taken at the output of the output stage of the CDA (‘incomplete feedback’). The complete feedback approach substantially suppresses the non-linearity of the inductor of the Lowpass filter as this filter now constitutes part of the feedback loop. The proposed approach is highly hardware efficient over reported prevalent complete feedback CDAs. When the proposed complete feedback CDA is compared against the prevalent incomplete feedback approach, the proposed CDA exhibited highly suppressed THD (∼40dB relative suppression in most cases). The THD of the proposed CDA is ≤0.012% for the complete modulation index range and pertinent input signal range. Means to further reduce the THD is also suggested.

Recent advances in the physical layer have enabled the simultaneous reception of multiple packets by a node in wireless networks. In this paper, we present a generalized model for the throughput optimization problem in wireless networks that support multi-packet reception (MPR) capability. Our model directly accounts for nodes with multiple transmitter antennas, which can be directional or omni-directional. We divide the problem into two subproblems: routing and scheduling. Due to the hardness of the scheduling subproblem, we propose a polynomial time heuristic based on a combination of greedy and linear programming paradigms. We use the devised scheme to study the impact of several design parameters on the performance of MPR-capable networks, including the number of interfaces, the beamwidth and the receiver range of the antennas. Numerical results demonstrate the effectiveness and the generality of the scheme, and permit us to draw valuable conclusions about MPR-capable networks.

Currently, vehicles are equipped with forward facing cameras to assist the forensic investigations of events by proactive image capturing from streets and roads. With content redundancy and storage imbalance in this in-network distributed storage system, how to maximize its storage capacity is a challenge. In other words, how to maximize the average lifetime of sensory data (i.e. images generated by cameras) in network is a fundamental problem need to be solved. This paper presents, VStore, a cooperative storage solution for mobile surveillance in vehicular sensor networks (VSN). The mechanisms in VStore are designed for redundancy elimination by exchanging information between vehicles and storage balancing. Compared with previous work, we deal with new challenges in mobile scenario. Field testing was carried out on a real-trace driven simulator, which utilizes about 500 taxies in Shanghai city. The testing results show that VStore can largely prolong the average lifetime of sensory data by cooperative storage.

In this paper, we present a linear programming formulation for the throughput optimization problem in wireless networks that support multi-packet reception (MPR) capability. The formulation takes into account the use of both directional and omni-directional antennas as well as the use of multiple transmitter interfaces per node. The joint routing and scheduling problem is decoupled into routing and scheduling subproblems. We show that the scheduling subproblem is intractable, and propose a polynomial time scheduling algorithm to solve it. We further demonstrate that, for certain type of networks, the completion time of the scheduling algorithm is at most two times the completion time of the the optimal scheduler, which is unknown. We use the proposed scheme for a preliminary study of several design parameters on the performance of MPR-capable networks, including the number of interfaces, the MPR capability and the beamwidth of the antennas.

The routing problem in wireless mesh networks is concerned with finding "good" source-destination paths. It generally faces multiple objectives to be optimized, such as i) path capacity, which accounts for the bits per second that can be sent along the path connecting the source to the destination node, and ii) end-to-end delay. This paper presents the mesh routing algorithm (MRA), a dynamic programming approach to compute high-capacity paths while simultaneously bounding the end-to-end delay. The proposed algorithm also provides the option of routing through multiple link-disjoint paths, such that the amount of traffic through each path is proportional to its capacity. Simulation results show that MRA outperforms other common techniques in terms of path capacity, while at the same time bounding the end-to-end delay to a desired value.

Currently, vehicular sensor network (VSN) has been paid much attention for monitoring the physical world of urban areas. We have studied VSNs by utilizing about 4000 taxies and 1000 buses equipped with GPS-based mobile sensors in Shanghai to constitute a virtual vehicular sensor network. The communication-connection intermittence makes the routing issue nontrivial when delay-tolerant applications are deployed in VSNs. The existing DTN routing protocols can be categorized as "neighbor-oriented" and how to select a neighbor candidate was always neglected. In this paper, we present a new DTN routing protocol for Delay-Tolerant Vehicular Sensor Networks, Packet-Oriented Routing protocol (POR), which is designed to emphasize neighbor selection based on awareness of packets to be sent and in consideration of probability to complete transferring of these packets. Our results show that POR performs much better than the ordinary Epidemic routing, as well as other popular routing protocols applied in a similar setting.

We study mechanism designs for resource management in service overlay, where services are provided by strategic agents. Usually, resources in distributed systems are limited. However, the current mechanism design does not take the capacity of agents into consideration. Traditionally, the Vickrey- Clarke-Groves (VCG) mechanism has been the only method to design protocols so that each strategic agent will follow the protocols for its own interest to maximize its benefit. We show that the VCG mechanism is not truthful anymore when the capacity of agents is limited. Thus, we have designed, based on non-uniform prices, a new capacity-aware mechanism which subsidizes the service agents so that each agent maximizes its profit if it truthfully reports its cost. Mechanisms for two widely used pricing models are designed and evaluated.

The existing vehicular sensors of taxi companies in most of cities can be used for traffic monitoring, however sensors are always set with a long sampling interval because of communication cost saving and network congestion avoidance. In this paper, we focus on the traffic data processing in vehicular sensor networks providing sparse and incomplete information. A performance evaluation study has been carried out in Shanghai by utilizing the sensors installed on 4000 taxis. Two types of traffic status estimation algorithms, the link-based and the vehicle-based, are introduced based on such data basis. The results from large-scale testing cases show that the traffic status can be fairly well estimated based on these imperfect data and we demonstrate the feasibility of such application in most of cities.

In this paper, the effects of power supply noise, qualified by power supply rejection ratio (PSRR), on two types of bridge-tied load (BTL) pulse width modulation (PWM) class D amps (denoted as Type-I BTL and Type-II BTL respectively) are investigated and the analytical expressions for PSRR of the two designs derived. The derived analytical expressions are verified by means of HSPICE simulations. The relationships derived herein provide good insight to the design of BTL class D amps, including how various parameters may be varied/optimized to meet a given PSRR specification. Furthermore, the PSRR of the two BTL Class D amps are compared against the single-ended class D amp, and the former designs show superior PSRR compared to the latter.

We present a mobile sensor system for traffic monitoring (GSSTM), which is a typically Grid application in ShanghaiGrid to provide accurate realtime traffic status information. Several issues and challenges in GSSTM are discussed, such as Grid architecture design, data processing for traffic status estimation, storage strategy of massive data, etc. We implemented a prototype system of GSSTM and carried out a field testing in Shanghai city by using GPS-based sensors on 4000 taxis. The testing results show that by utilizing the Grid technology, the expected performance can be obtained, such as stability, scalability, etc. Meantime, traffic status can be fairly well estimated in GSSTM.

In performance studies of vehicular ad hoc networks (VANETs), the underlying mobility model plays an important role. Since conventional mobile ad hoc network (MANET) routing protocols do not work efficiently in vehicular environments due to the rapid topology changes, the Delay-Tolerant Network (DTN) model is often applied. In this paper, we construct a new mobility model, the Shanghai Urban Vehicular Network (SUVnet) model by using the GPS data from more than 4,000 taxis we have collected, and then investigate the performance of two kinds of DTN routing, the non-geographic pure epidemic routing and our newly-proposed geographic DTN routing, the Distance-Aware Epidemic Routing (DAER). We use the popular random waypoint mobility model and a more complex microscopic traffic simulator generated model for performance comparison. With the two considered DTN routing protocols, conventional mobility models tend to give higher performance results than SUVnet model, the presumably more realistic mobility model.

A disruption-tolerant network (DTN) attempts to route packets between nodes that are temporarily connected. Difficulty in such networks is that nodes have no information about the network status and contact opportunities. The situation is different in public bus networks because the movement of buses exhibits some regularity so that routing in a deterministic way is possible. Many algorithms use a contacts oracle that provides the exact meeting times and durations between all nodes. However, in a real vehicular environment, an oracle is not always accurate, and deterministic routing gives poor results. In this paper, we present BLER, a routing algorithm that achieves effective routing in a buses environment. BLER, compared to other algorithms, performs routing at bus line level instead of bus level; it uses specific bus lines information to achieve good performances. We evaluate BLER on real traces of the bus network of Shanghai, and compare it to other routing algorithms. Performances provide good results for this kind of DTNs.

This paper presents the FFT (flip-flop tone) DMAC protocol, a tone based MAC protocol using directional antennas to solve the deafness problem, hidden terminal and exposed terminal problems simultaneously. It uses two pairs of flip-flop tones. The first pair of tone is sent omni-directionally to reach every neighboring node to announce the start and the end of communication, and therefore to avoid the deafness problem. The second pair of tone is sent directionally towards the sender. It is used to solve the hidden terminal problem as well as the exposed terminal problem. Evaluation shows that FFT-DMAC can achieve better performance compared to the 802.11 and ToneDMAC protocol.

In this paper, the effect of power supply noise, qualified by power supply rejection ratio (PSRR), on bang-bang control class D amplifier (BCCD) is investigated. By modeling the BCCD with power supply noise, the mechanisms are modeled. Further, by means of a novel analysis based on a double-Fourier series, the parameters related to power supply noise is derived and thereafter expressions for PSRR are derived. The analyses are verified by means of computer simulations and by measurements on practical circuits. The relationships derived herein provide good insight to the design of BCCDs, including how various parameters may be varied/optimized to meet a given PSRR specification.

It is crucial to design algorithms for energy-efficient query processing for a sensor network since sensor nodes are battery-powered, and thus their lifetimes are limited. We propose a history-based approach to optimizing query processing. We apply the approach to the top-k query problem and design new algorithms. Energy consumption can be reduced by pruning unnecessary sub-queries or guiding the query to right directions. Simulation results show that energy cost can be significantly reduced. This approach can be generalized for other query problems.

In this work, we study the topology enhancement problem of wireless sensor networks. Our research focuses on reducing the path-based vulnerability. The objective is to get as much information as possible for any target moving out of the surveillance area. We study intelligent targets that have the knowledge of existing sensor distribution. Under such assumption, we find the vulnerable paths that rational targets would like to take and block these paths to enhance the network detection performance. Simulation shows that by adding only a few numbers of new sensors on specific positions, we can greatly decrease the vulnerability of a randomly deployed sensor network.

In this paper, we propose and derive a linear model of a closed-loop PWM class D amplifier (CDA) to model its power supply rejection ratio (PSRR). On the basis of the proposed model, we derive a simple expression that depicts the effects of 3 critical parameters on PSRR: the gain of the integrator, the gain of the PWM stage and the feedback factor. We recommend, from a practical viewpoint, that the first and third parameters be increased if higher PSRR is desired. We validate our model and analysis on the basis of HSPICE simulations and on experimental measurements. Our model and analysis are useful as they provide insight to a CDA designer, in particular how various parameters may be varied/compromised to meet a given set of PSRR specifications

We derive Fourier series expressions for modeling analog closed-loop PWM class D amplifiers. Based on our derived expressions, we are able to analyze the mechanisms of several nonlinearities, specifically the power supply noise and fold-back distortions. We investigate the influence of the finite loop gain on these nonlinearities, and we show that those nonlinearities can be effectively suppressed by the higher loop gain. We verify our analysis by computer simulations and also on the basis of experimental measurements. The derived expressions are practically useful as they provide insights to a designer for PWM class D amplifier designs

Continuous media, such as digital movies, video clips, and music, are becoming an increasingly common way to convey information, entertain and educate people. However, limited system and network resources have delayed the widespread usage of continuous media. Most existing on-demand services are not scalable for a large content repository. In this paper, we propose a scalable and inexpensive video delivery scheme, named Scheduled Video Delivery (SVD). In the SVD scheme, users submit requests with a specified start time. Incentives are provided so that users will specify the start times that reflect their real needs. The SVD system combines requests to form the multicasting groups and schedules these groups to meet the deadline. SVD scheduling has a different objective from many existing scheduling schemes. Its focus has been shifted from minimizing the waiting time toward meeting deadlines and at the same time combining requests to form multicasting groups. SVD compliments most existing video delivery schemes as it can be combined with them. It requires much less resources than other schemes. Simulation study for the SVD performance and the comparison to other schemes are presented.

Sensor networks are expected to find widespread use in a variety of applications. In the near future, more and more sensor networks will be deployed for multiple services in a surrounding area. Different sensor networks may overlap or partially overlap with each other, and may interfere with each other. However, it also provides an opportunity to construct a low energy, high connectivity, and more robust sensor network. We propose an InterSensorNet scheme, which is a federation of multiple sensor networks. The success of the InterSensorNet depends on whether a node is willing to cooperate with nodes in a foreign network. What will be the incentive to do so? With concepts from economics and game theory, we propose a mechanism design (MD) approach to handle the strategic agents that respond to incentives. We apply MD to two practical setting of multiple sensor networks and study applications of InterSensorNet mechanism design.

To turn an ideal mobile sensor network simulation model into reality, terrain is one of the inevitable factors we have to consider. This work is the first attempt to address this issue, by studying the behavior of mobile sensors under constraints of terrain. Specifically, we study the power consumption and the loss ratio of mobile sensors when they are moving on different terrains. These two metrics are utilized to select the best destinations, the best paths to the destinations, and match these destinations with mobile sensors.

RPP is a distributed routing mechanism for wireless ad hoc networks with strategic agents. A strategic agent is rational but selfish and has its own incentive to route traffic for other agents. Forwarding data is definitely not the self-interest of an agent due to consumption of battery. However, if no agent is willing to forward data for others, the ad hoc network itself will break. In this paper, a routing mechanism is designed such that maximizing the benefit of each strategic agent leads to a global optimal system. In this mechanism, an agent accepts payments for forwarding data for other agents if the payment covers their costs. The payment is computed recursively to obtain a cost-efficient and truthful mechanism. The overpayment in current mechanisms is completely removed. Analysis and simulation results are also provided.

Overlay multicast has drawn a lot of attention as an alternative to IP multicast. In the recently proposed overlay multicast solution, most of the implementations do not address the inter-domain administrative issue. For wide area multicast, it is unavoidable to have communication among several administrative domains. At this time, multicast routing cannot assume the knowledge of the global network topology, nor can it ignore the routing policy constrained by contractual commercial agreement between administrative domains. This problem can be solved by an hierarchical organization of the routing infrastructure. We propose a zone approach to overlay multicast that performs hierarchical routing on two levels - one level for within each of the administrative domains and another level for among the domains. We compare a single centralized routing to our zone-approach routing for overlay multicast and demonstrate that the performance penalty for the hierarchical organization of routing is small. The results have shown that our distributed design can achieve very close performance to the centralized algorithm. At the same time it enables the composition of different administrative networks, each with its own independent multicast protocol and administrative policy.

Multicast is important for realtime delivery of popular streaming media. Proxy-based multicast is an approach to implementing the multicast function by proxy servers at application levels. Many routing algorithms have been proposed to build an overlay network when proxy locations have been determined. On the other hand, the problem of where to place proxies has not been extensively studied yet. A study on the placement problem for proxy-based multicast is presented in this paper. Performance metrics are studied. A number of algorithms are proposed for multicast proxy placement and their performance is compared.

Scalability is a key issue of on-line video service. Different methods have been proposed for the closed-loop video service, such as batching and patching. However, scalability itself has not been formally defined and the condition for a scalable system is not well studied yet. This paper studies scalability and the condition for scalable systems. It is found that when the arrival rate is across the threshold /spl Theta/ the system becomes scalable. This threshold value depends only on the number of videos, video length, and request distribution. We present an analysis for batching and patching. Comparison of batching, patching, and a new method, scheduled video delivery (SVD), is presented in this paper.

A video distribution architecture with edge stations and Wi-Fi delivery networks as connection to residential homes is described in this paper. An edge station is configurable and controllable by a central server. It is placed in the access point of Wi-Fi networks and has multiple usages. Due to its large storage space it can be used as a mirroring/caching proxy for continuous media. Replicating popular video contents in many small mirroring sites can significantly reduce the network bandwidth requirement. When this structure is used with a cable or hybrid fiber/coax (HFC) network, it turns to be a hybrid fiber/coaxAVi-Fi (HFCW) structure, particularly suitable for video-on-demand (VoD) applications. There are many advantages of this architecture. First, the central server load and network traffic can be reduced to a small percentage. Second, the response time of most video playing requests can be significantly reduced. Third, true VoD can possibly be provided with a one-way cable system. Finally, noise from STBs (set-top boxes) is absorbed by the edge station in a two-way cable system.

In contrast to one-to-one unicast transmission, multicast provides a one-to-many transmission paradigm. The overlay multicast has drawn a lot of attention as an alternative to IP multicast. In this paper, we compare four typical implementations of overlay multicast: Scattercast, Narada, overcast and ALMI. Several metrics are compared which are applicable to these projects, including relative delay penalty, normalized resource usage and stress. We evaluate those projects in a uniform network environment and discuss how the design approach and structure affects the performance.

Abstract Video servers are essential in video‐on‐demand and other multimedia applications. In this paper, we present our high‐performance clustered CBR video server, Odyssey. Odyssey is a server connecting PCs with switched Ethernet. It provides efficient support for normal play and interactive browsing functions such as fast‐forward and fast‐backward. We designed a set of algorithms for scheduling, synchronization and admission control, which results in a high utilization of resources. Odyssey is able to deliver a large number of video streams. Copyright © 2003 John Wiley & Sons, Ltd.

Most existing on-demand video services, such as VoD, batching and patching, are not scalable. Although the near VoD service is scalable, it can provide only dozens of videos. A scalable video delivery paradigm, named scheduled video delivery (SVD), is described. In the SVD paradigm, users submit requests with specification of start time. The SVD system combines requests to form multicasting groups and schedules these groups to meet the deadline. SVD is not only scaled to the number of users but also to the number of video objects. Furthermore, SVD can serve more clients with mirroring proxies.

Continuous media, such as digital movies, video clips, and music, are becoming an increasingly common way to present information, entertain and educate people. However, limited system and network resources have delayed the widespread usage of continuous media. In this paper, we propose a scalable and inexpensive video delivery paradigm, named Scheduled Video Delivery (SVD). In the SVD paradigm, users submit requests with specification of start time. The provider schedules these requests to meet the QoS specification and to maximize utilization of the resources. SVD scheduling has a different objective from many existing scheduling schemes. It does not aim at minimizing the waiting time. Instead, it focuses on meeting deadlines and at the same time combining requests to form multicasting groups. SVD scales not only to the number of users but also to the number of video objects.

True minutiae extraction in fingerprint image is critical to the performance of an automated identification system. Generally, a set of endings and bifurcations (both called feature points) can be obtained by the thinning image from which the true minutiae of the fingerprint are extracted by using the rules based on the structure of ridges. However, considering some false and true minutiae have similar ridge structures in the thinning image, in a lot of cases, we have to explore their difference in the binary image or the original gray image. In this paper, we first define the different types of feature points and analyze the properties of their ridge structures in both thinning and binary images for the purpose of distinguishing the true and false minutiae. Based on the knowledge of these properties, a fingerprint post-processing approach is developed to eliminate the false minutiae and at the same time improve the thinning image for further application. Many experiments are performed and the results have shown the great effectiveness of the approach.

Providing efficient support for interactive browsing operations such as fast-forward (ff) and fast-backward (fb) is essential in video-on-demand and other multimedia server systems. In this paper, we propose two basic approaches to scheduling interactive browsing operations: 1) the prefetching approach and 2) the grouping approach. Block-skipping and frame-skipping algorithms are presented for constant bit rate (CBR) data blocks. These algorithms can precisely schedule video streams for both normal play and interactive browsing operations.

A mapping algorithm for heterogeneous computing systems is proposed in this paper. This algorithm utilizes a new indicator-the relative cost-to obtain optimal mapping. The existing Min-min algorithm can be well explained under synergy of this new indicator. It is found that the Min-min algorithm leaves room for improvement because of its haste to reduce completion time by overlooking the impact of load balance. Our new algorithm retains the advantages of the Min-min algorithm and balances the load very well. It demonstrates the ability to generate good mapping in various heterogeneous environments.

Scheduling DAGs to multiprocessors is one of the key issues in high-performance computing. Most realistic scheduling algorithms are heuristic and heuristic algorithms often have room for improvement. The quality of a scheduling algorithm can be effectively improved by a local search. In this paper, we present a fast local search algorithm based on topological ordering. This is a compaction algorithm that can effectively reduce the schedule length produced by any DAG Scheduling algorithm. Thus, it can improve the quality of existing DAG scheduling algorithms. This algorithm can quickly determine the optimal search direction. Thus, it is of low complexity and extremely fast.

A runtime parallel incremental DAG scheduling approach is described in this paper. A DAG is expanded incrementally, scheduled, and executed on a parallel machine. A DAG scheduling algorithm is parallelized to scale to large systems. In this approach, a large DAG can be executed without consuming large amount of memory space. Inaccurate estimation of task execution time and communication time can be tolerated. This runtime approach can also execute dynamic DAGs. Implementation of this parallel incremental system demonstrates the feasibility of this approach. Preliminary results show that it is superior to other approaches.

In this paper, we present the performance result and analysis of parallel CBR video servers with conflict-free scheduling algorithms and server synchronization at time slot and time cycle levels.The experimental outcome shows that by relaxing serverlevel synchronization to a time cycle, the conflict-free slot scheduling produces higher stream throughput than the cycle scheduling.

As the important implementation of biometric technology, palmprint verification is one of the most reliable personal identification methods. In this paper, a new approach to palmprint verification based on line feature matching and datum point invariance is presented. The datum points of palmprint which act as the important registrations, are defined owing to their remarkable advantage of invariable location. Then, the simple and efficient methods of line feature extraction and matching are proposed. Several palmprint images are adopted to test the approach and the experimental results show the effectiveness of palmprint verification.

This paper presents scheduling algorithms for normal and interactive playout in parallel video servers. These algorithms include conflict-free scheduling, delay minimization, and request relocation for normal playout, as well as prefetching and grouping for interactive operations. Performance is presented for these algorithms.

The lack of a versatile software tool for parallel program development has been one of the major obstacles for exploiting the potential of high-performance architectures. In this paper, we describe an experimental software tool called CASCH (Computer Aided SCHeduling) for parallelizing and scheduling applications to parallel processors. CASCH transforms a sequential program to a parallel program with automatic scheduling, mapping, communication, and synchronization. The major strength of CASCH is its extensive library of scheduling and mapping algorithms representing a broad range of state-of-the-art work reported in the recent literature. These algorithms are applied for allocating a parallelized program to the processors, and thus the algorithms can be interactively analyzed, tested and compared using real data on a common platform with various performance objectives. CASCH is useful for both novice and expert programmers of parallel machines, and can serve as a teaching and learning aid for understanding scheduling and mapping algorithms.

Scheduling DAGs to multiprocessors is one of the key issues in high-performance computing. Local search can be used to effectively improve the quality of a scheduling algorithm. In this paper, based on topological ordering, we present a fast local search algorithm which can improve the quality of DAG scheduling algorithms. This low complexity algorithm can effectively reduce the length of a given schedule.

Most static algorithms that schedule parallel programs represented by macro dataflow graphs are sequential. This paper discusses the essential issues pertaining to parallelization of static scheduling and presents two efficient parallel scheduling algorithms. The proposed algorithms have been implemented on an Intel Paragon machine and their performances have been evaluated. These algorithms produce high-quality scheduling and are much faster than existing sequential and parallel algorithms.

Runtime Incremental Parallel Scheduling (RIPS) is an alternative strategy to the commonly used dynamic scheduling. In this scheduling strategy, the system scheduling activity alternates with the underlying computation work. RIPS utilizes the advanced parallel scheduling technique to produce a low overhead, high quality load balancing, as well as adapting to irregular applications. The paper presents methods for scheduling a single job on a dedicated parallel machine.

Runtime incremental parallel scheduling (RIPS) is a new approach for load balancing. In parallel scheduling, all processors cooperate together to balance the workload. Parallel scheduling accurately balances the load by using global load information. In incremental scheduling, the system scheduling activity alternates with the underlying computation work. RIPS produces high-quality load balancing and adapts to applications of nonuniform structures. This paper presents methods for scheduling a single job on a dedicated parallel machine.

One of the essential problems in parallel computing is: Can SIMD machines handle asynchronous problems? This is a difficult, unsolved problem because of the mismatch between asynchronous problems and SIMD architectures. We propose a solution to let SIMD machines handle general asynchronous problems. Our approach is to implement a runtime support system which can run MIMD-like software on SIMD hardware. The runtime support system, named P kernel, is thread-based. There are two major advantages of the thread-based model. First, for application problems with irregular and/or unpredictable features, automatic scheduling can move some threads from overloaded processors to underloaded processors. Second, and more importantly, the granularity of threads can be controlled to reduce system overhead. The P kernel is also able to handle bookkeeping and message management, as well as to make these low-level tasks transparent to users. Substantial performance has been obtained on Maspar MP-1.>

One of the essential problems in parallel computing is: can STMD machines handle asynchronous problems? Thas is a dificult, unsolved problem because of the mismatch between asynchronous problems and SIMD archtiectures. We propose a soluiaon to let SIMD machines handle general asynchronous problems. Our approach is to implement a runtime support system which can run MIMD-like software on SIMD hardware. Substantial performance has been obtained on CM-2 and CM-5.

A net-merging method is proposed for gate-matrix layout. The method is based on a density function to calculate the minimum number of tracks necessary for the net assignment. Examples that demonstrate how this method leads to a denser gate matrix layout are included. The pitch of the gate columns is determined by the design rules, in particular, the space required to accommodate a diffused region with an internal contact window between two poly columns. In gate matrix layout, when the space between a pair of gate columns is not sufficient, the spacing between them can be increased locally to two pitches to avoid design rule violation as long as such a local change does not cause column matching problems.>