To maximize the utility of lecture videos, in today’s fast-paced society with dwindling attention spans, various e-learning technologies are introduced, e.g., non-linear learning, bite-sized learning, and personalized lecture video fragment recommendation. In this article, we conduct a detailed performance study on a key enabler for aforementioned technologies: Lecture Video Fragmentation by Key Point Identification in lecture videos. We begin with a taxonomy of existing methods, which are classified into two categories: boundary-based methods, where the fragmentation is achieved using specific methods depending on the modality, and representation-based methods, where the fragmentation task is formulated as a boundary prediction task based on representations of smaller video chunks. Various configurations of these methods are also examined in detail. To conduct an extensive, comprehensive, and objective comparison study, we address the limitations of existing datasets by introducing a new lecture video fragmentation dataset, MITFLD, without any synthetic videos. We also propose a unified framework kpi , which includes the implementation of datasets, metrics, and compared methods to facilitate the experiments and future research on lecture video fragmentation. The experiments cover different configurations of existing methods on two large datasets (AVLecture and MITFLD). Further experiments are also conducted for ablation studies, such as the effect of feature combinations and the influence of lecture modes. Through the experiments, the representation-based method BiLSTM with self-supervised learning representations is found to exhibit promising performance. Key insights and potential future directions are also discussed.

In today’s fast-paced digital landscape, the attention span of users consuming video content is alarmingly brief, often as short as 15 seconds for music or entertainment videos and 6 minutes for lecture videos. This presents a significant challenge for video producers and platform providers as they seek to engage users with longer content. One promising solution involves recommending specific fragments within longer videos that align with individual user profiles. In this article, we address this challenge by introducing a novel framework for video fragment recommendations, guided by three key insights. First, we implement a Self-Attention Block that captures the inter-fragment contextual effect, enhancing the relevance of recommendations. Second, we incorporate video-level preferences to ensure that the fragment recommendations are consistent with users’ overall interests. Third, we propose a Self-Attentive Herding Effect (SAHE) module to model the intra-fragment contextual effect, specifically the herding effect of time-sync comments within a fragment. To evaluate the effectiveness of our proposed method, we conduct extensive experiments comparing our model against the state-of-the-art approaches in terms of NDCG@K and Recall@K. Our results demonstrate that the model effectively leverages inter-fragment and intra-fragment contextual effects along with video-level preferences, outperforming existing methods. Additionally, we carry out empirical experiments to analyze the key components and parameters of the proposed model, providing further insights into its performance. 1

The emerging applications for smart cities intend to promote the quality of citizens’ life. Among them, ubiquitous user connectivity and real-time computation offloading are significant for the ever-increasing requirements of delay-sensitive and mission-critical applications. By integrating human social behaviors (such as relationship, similarity, community, and social ties) with physical Internet of Things (IoT) systems, social IoT systems are promising to provide ubiquitous connectivity among users. As the applications of social IoT systems are transferring from information dissemination to user entertainment (such as image identification, online games, and augmented reality), computation offloading is significant to reduce the execution delay of applications.

It is critical to reduce the operating cost of shared buses for bus companies and improve the user experience of passengers. However, existing studies focus on either bus scheduling or route planning, which cannot accomplish the above mentioned goals concurrently. In this paper, we construct a joint bus scheduling and route planning framework to maximize the number of passengers, minimize the total length of routes and the number of required buses, as well as guarantee good user experience of passengers. First, we establish a system model based on a real-world scenario and formulate a multi-objective combinational optimization problem. Then, based on the extracted traffic topology of urban traffic networks and the generated candidate line set, we propose an offline algorithm to cope with the similar passenger flow distributions, e.g., morning or evening peak of every day. In order to cope with dynamic real-time passenger flows, an online algorithm is designed. Experiments are carried out based on real-word scenarios. The results show that the proposed algorithms can greatly reduce the operating cost of bus companies and guarantee good user experience based on real-world scheduling data in comparison with several existing methods.

A variety of novel mobile applications are developed to attract the interests of potential users in the emerging 5G-enabled vehicular networks. Although computation offloading and task scheduling have been widely investigated, it is rather challenging to decide the optimal offloading ratio and perform adaptive task scheduling in high-dynamic networks. Furthermore, the scheduling policy made by the network operator may be violated, since vehicular users are rational and selfish to maximize their own profits. By considering the incentive compatibility and individual rationality of vehicular users, we present POETS, an efficient partial computation offloading and adaptive task scheduling algorithm to maximize the overall system-wide profit. Specially, a two-sided matching algorithm is first proposed to derive the optimal transmission scheduling discipline. After that, the offloading ratio of vehicular users can be obtained through convex optimization, without any information of other users. Furthermore, a non-cooperative game is constructed to derive the payoff of vehicular users that can reach the equilibrium between users and the network operator. Theoretical analyses and performance evaluations based on real-world traces of taxies demonstrate the effectiveness of our proposed solution.

Intelligent Transportation System (ITS) is critical to cope with traffic events, e.g., traffic jams and accidents, and provide services for personal traveling. However, existing researches have not jointly considered the user data safety, utility and system latency comprehensively, to the best of our knowledge. Since both safe and efficient transmissions are significant for ITS, we construct a blockchain-enabled crowdsensing framework for distributed traffic management. First, we illustrate the system model and formulate a multi-objective optimization problem. Due to its complexity, we decompose it into two subproblems, and propose the corresponding schemes, i.e., a Deep Reinforcement Learning (DRL)-based algorithm and a DIstributed Alternating Direction mEthod of Multipliers (DIADEM) algorithm. Extensive experiments are carried out to evaluate the performance of our solutions, and experimental results demonstrate that the DRL-based algorithm can legitimately select active miners and transactions to make a satisfied trade-off between the blockchain safety and latency, and the DIADEM algorithm can effectively select task computation modes for vehicles in a distributed way to maximize their social welfare.

The prompt evolution of Internet of Medical Things (IoMT) promotes pervasive in-home health monitoring networks. However, excessive requirements of patients result in insufficient spectrum resources and communication overload. Mobile Edge Computing (MEC) enabled 5G health monitoring is conceived as a favorable paradigm to tackle such an obstacle. In this paper, we construct a cost-efficient in-home health monitoring system for IoMT by dividing it into two sub-networks, i.e., intra-Wireless Body Area Networks (WBANs) and beyond-WBANs. Highlighting the characteristics of IoMT, the cost of patients depends on medical criticality, Age of Information (AoI) and energy consumption. For intra-WBANs, a cooperative game is formulated to allocate the wireless channel resources. While for beyond-WBANs, considering the individual rationality and potential selfishness, a decentralized non-cooperative game is proposed to minimize the system-wide cost in IoMT. We prove that the proposed algorithm can reach a Nash equilibrium. In addition, the upper bound of the algorithm time complexity and the number of patients benefiting from MEC is theoretically derived. Performance evaluations demonstrate the effectiveness of our proposed algorithm with respect to the system-wide cost and the number of patients benefiting from MEC.

Due to line-of-sight communication links and distributed deployment, Unmanned Aerial Vehicles (UAVs) have attracted substantial interest in agile Mobile Edge Computing (MEC) service provision. In this paper, by clustering multiple users into independent communities based on their geographic locations, we design a 5G-enabled UAV-to-community offloading system. A system throughput maximization problem is formulated, subjected to the transmission rate, atomicity of tasks and speed of UAVs. By relaxing the transmission rate constraint, the mixed integer non-linear program is transformed into two subproblems. We first develop an average throughput maximization-based auction algorithm to determine the trajectory of UAVs, where a community-based latency approximation algorithm is developed to regulate the designed auction bidding. Then, a dynamic task admission algorithm is proposed to solve the task scheduling subproblem within one community. Performance analyses demonstrate that our designed auction bidding can guarantee user truthfulness, and can be fulfilled in polynomial time. Extensive simulations based on real-world data in health monitoring and online YouTube video services show that our proposed algorithm is able to maximize the system throughput while guaranteeing the fraction of served users.

The papers in this special section focus on pervasive edge computing (PEC)for industrial Internet of Things. With the development of 5G technology and intelligent terminals, computation, communication, and storage capacities of devices are largely improved. Based on that, pervasive edge computing (PEC) becomes possible, where data can be processed on the network edge with the assistant of those intelligent terminals enhanced by 5G technology except the management of any centralized servers, including clouds and remote servers. The papers in this section solicits original research and practical contributions which advance PEC in industrial IoTs (IIoTs), regarding the architecture, technologies, and applications.

Recently, Internet of Vehicles (IoV) has become one of the most active research fields in both academic and industry, which exploits resources of vehicles and Road Side Units (RSUs) to execute various vehicular applications. Due to the increasing number of vehicles and the asymmetrical distribution of traffic flows, it is essential for the network operator to design intelligent offloading strategies to improve network performance and provide high-quality services for users. However, the lack of global information and the time-variety of IoVs make it challenging to perform effective offloading and caching decisions under long-term energy constraints of RSUs. Since Artificial Intelligence (AI) and machine learning can greatly enhance the intelligence and the performance of IoVs, we push AI inspired computing, caching and communication resources to the proximity of smart vehicles, which jointly enable RSU peer offloading, vehicle-to-RSU offloading and content caching in the IoV framework. A Mix Integer Non-Linear Programming (MINLP) problem is formulated to minimize total network delay, consisting of communication delay, computation delay, network congestion delay and content downloading delay of all users. Then, we develop an online multi-decision making scheme (named OMEN) by leveraging Lyapunov optimization method to solve the formulated problem, and prove that OMEN achieves near-optimal performance. Leveraging strong cognition of AI, we put forward an imitation learning enabled branch-and-bound solution in edge intelligent IoVs to speed up the problem solving process with few training samples. Experimental results based on real-world traffic data demonstrate that our proposed method outperforms other methods from various aspects.

Recent developments of edge computing and content caching in wireless networks enable the Intelligent Transportation System (ITS) to provide high-quality services for vehicles. However, a variety of vehicular applications and time-varying network status make it challenging for ITS to allocate resources efficiently. Artificial intelligence algorithms, owning the cognitive capability for diverse and time-varying features of Internet of Connected Vehicles (IoCVs), enable an intent-based networking for ITS to tackle the above-mentioned challenges. In this paper, we develop an intent-based traffic control system by investigating Deep Reinforcement Learning (DRL) for 5G-envisioned IoCVs, which can dynamically orchestrate edge computing and content caching to improve the profits of Mobile Network Operator (MNO). By jointly analyzing MNO's revenue and users' quality of experience, we define a profit function to calculate the MNO's profits. After that, we formulate a joint optimization problem to maximize MNO's profits, and develop an intelligent traffic control scheme by investigating DRL, which can improve system profits of the MNO and allocate network resources effectively. Experimental results based on real traffic data demonstrate our designed system is efficient and well-performed.

The explosive growth of mobile devices promotes the prosperity of novel mobile applications, which can be realized by service offloading with the assistance of edge computing servers. However, due to limited computation and storage capabilities of a single server, long service latency hinders the continuous development of service offloading in mobile networks. By supporting multi-server cooperation, Pervasive Edge Computing (PEC) is promising to enable service migration in highly dynamic mobile networks. With the objective of maximizing the system utility, we formulate the optimization problem by jointly considering the constraints of server storage capability and service execution latency. To enable dynamic service placement, we first utilize Lyapunov optimization method to decompose the long-term optimization problem into a series of instant optimization problems. Then, a sample average approximation-based stochastic algorithm is proposed to approximate the future expected system utility. Afterwards, a distributed Markov approximation algorithm is utilized to determine the service placement configurations. Through theoretical analysis, the time complexity of our proposed algorithm is linear to the number of users, and the backlog queue of PEC servers is stable. Performance evaluations are conducted based on both synthetic and real trace-driven scenarios, with numerical results demonstrating the effectiveness of our proposed algorithm from various aspects.

The automated diagnosis helps us better understand the complex landscape of diseases, leading to more effective, early and reliable medical diagnosis and therapy. The human-machine interactions in healthcare delivery relying on automated cyber-physical systems (ACPSs) play an important role in the automated diagnosis. Currently, the multicore accelerator used for ACPS has utilized the network-on-chip (NoC) for personalized healthcare. However, the discrete cores based on NoC are affected by limited computation speed, since the data have to pass through an electrical interconnect. In this paper, we propose a novel optical NoC (ONoC) solution of designing discrete cores to quickly understand biomarkers for early detecting abnormal pathophysiology, such as the deviation from the protein's native state. We analyze the performance of our ONoC-based ACPS accelerator for personalized healthcare by virtue of the tested proteins widely adopted in the lattice protein model. Our mathematical analysis and simulation results demonstrate that: 1) the chip area becomes smaller than a traditional design, which makes the personalized healthcare product more convenient; 2) the computation speed is promoted, resulting in the rapid understanding of biomarkers; and 3) we improve the data transmission reliability through accurately capturing the photonic effect so that desirable human-machine interactions can be guaranteed. Note to Practitioners-We design an on-chip hardware accelerator for automated diagnosis and personalized healthcare by predicting biological protein folding. The simulation results based on the lattice protein model can well guide the practitioners to design a more convenient and reliable product quickly detecting the biomarker, such as the deviation from the protein's native state.

There are existing multi-MOOC level dropout prediction research in which many MOOCs' data are involved. This generated good results, but there are two potential problems. On one hand, it is inappropriate to use which week students are in to select training data because courses are with different durations. On the other hand, using all other existing data can be computationally expensive and inapplicable in practice.

As an emerging communication platform, opportunistic Cloud of Things (CoT) is promising for clients to exchange messages through opportunistic contacts in cloud computing-enabled Internet of Things. Recently, numerous socially aware schemes have been put forward, leveraging users’ social attributes and contact history to predict future contacts with the purpose of improving message forwarding efficiency and network throughput. However, individual privacy is generally overlooked in the prediction process and transmission stage of opportunistic CoT. In this paper, we construct a privacy-preserving message forwarding framework for opportunistic CoT to guarantee individual privacy and improve transmission efficiency. We first set up a two-layer architecture of a cloud server to improve communication efficiency for terminal clients. By integrating a security-based mobility prediction algorithm with a routing decision process, our scheme can effectively protect individual privacy. We integrate an attribute-based cryptographic algorithm with a message delivery process to enable our scheme to resist attacks, such as Sybil attack, drop for profit, and data tampered attack. Compared with some existing solutions, our scheme improves network security significantly at the cost of slightly increased communication overhead.

Sharing economy refers to peer-based activities of obtaining, giving, or sharing the access to goods and services, coordinated through community-based online services. It is known as collaborative consumption that people share the services rather than having individual ownership. By leveraging idle resources to produce more goods and services, sharing economy significantly drives green consumption and sustainable development in our human society. Using information technology to provide individuals with information enables the optimization of resources through the mutualization of excess capacity in goods and services. A common premise is that when information is shared, the value of the goods may increase for businesses, for individuals, for communities, and for the whole society in general. Currently, sharing economy has potentially resulted in a great impact on citizens’ everyday life and generated huge economic benefits, e.g., Airbnb, Uber, and Amazon Mechanical Turk. A host of enabling technologies has reached the mainstream for the rise of sharing economy, including open data, the ubiquity of low-cost mobile phones, and social media. These technologies dramatically reduce the friction of share-based business and organizational models.

CypherDB addresses the problem of protecting the confidentiality of database stored externally in a cloud and enabling efficient computation over it to thwart any curious-but-honest cloud computing service provider. It works by encrypting the entire outsourced database and executing queries over the encrypted data using our novel CypherDB secure processor architecture. To optimize computational efficiency, our proposed processor architecture provides tightly-coupled datapaths that avoid information leakage during database access and query execution. Our simulation using a well-known database benchmark TPC-H over a commercial grade Database Management System (SQLite) demonstrates that our proposed architecture incurs an average of about 10 percent overhead when compared with the same set of operations without secure database processing.

Massive Open Online Courses (MOOCs) have recently been highly popular among worldwide learners, while it is challenging to manage and interpret the large-scale discussion forum which is the dominant channel of online communication. K-Means clustering, one of the famous unsupervised learning algorithms, could help instructors identify influential users in MOOC forum, to better understand and improve online learning experience. However, traditional K-Means suffers from bias of outliers and risk of falling into local optimum. In this paper, OP-DCI, an optimized K-Means algorithm is proposed, using outlier post-labeling and distant centroid initialization. Outliers are not solely filtered out but extracted as distinct objects for post-labeling, and distant centroid initialization eliminates the risk of falling into local optimum. With OP-DCI, learners in MOOC forum are clustered efficiently with satisfactory interpretation, and instructors can subsequently design personalized learning strategies for different clusters.

Nonlinear model order reduction has always been a challenging but important task in various science and engineering fields. In this paper, a novel symmetric tensor-based order-reduction method (STORM) is presented for simulating large-scale nonlinear systems. The multidimensional data structure of symmetric tensors, as the higher order generalization of symmetric matrices, is utilized for the effective capture of high-order nonlinearities and efficient generation of compact models. Compared to the recent tensor-based nonlinear model order reduction (TNMOR) algorithm [1], STORM shows advantages in two aspects. First, STORM avoids the assumption of the existence of a low-rank tensor approximation. Second, with the use of the symmetric tensor decomposition, STORM allows significantly faster computation and less storage complexity than TNMOR. Numerical experiments demonstrate the superior computational efficiency and accuracy of STORM against existing nonlinear model order reduction methods.

This paper proposes an automatic chord estimation (ACE) system with a two-layer architecture. The first layer performs chord smoothing with "GMM + HMM" approach. Then given the results of the first layer, the second layer performs chord estimation using a deep neural network, which is trained on a well chord-type balanced dataset. The system accepts exactly the "SeventhsBass" vocabulary. Three approaches with different configurations of the system are compared with Chordino, which is probably the only both MIREX evaluated and "SeventhsBass" acceptable ACE system. Evaluation results on "The Beatles" dataset show that the best approach outperforms Chordino in the most difficult "SeventhsBass" metric in a significant way.

Millions of people are severely injured or killed in road accidents every year and most of these accidents are caused by human error. Fatigue and negative emotions such as anger adversely affect driver performance, thereby increasing the risk involved in driving. Research has shown that listening to the right kind of music in these situations can ameliorate driver performance and improve road safety. Context-aware music delivery systems succeed in delivering suitable music according to the situation through the process of music mood-mapping which identifies the mood of a song. Additionally, we can leverage the power of the cloud to enable crowd sensing of the mood-mapping of various songs and enhance the effectiveness of situation-aware music delivery for drivers. The cloud can be used to aggregate the crowd sensed music mood-mapping data and improve the effectiveness of music delivery by providing accurate mood-mappings from the aggregated data. Currently, context-aware music delivery systems consider only features from the song for music mood-mapping. In this paper, we propose a novel approach to music mood-mapping for drivers which also incorporates the social context of a driver including age, gender and cultural background to enhance the effectiveness of music delivery in context-aware music recommendation systems for drivers.

Many applications use encryption to protect data confidentiality, which require decryption before any data processing. Integrating ASIC design of encryption engines and general-purpose processor can yield the best overall performance in program execution as it benefits from low latency hardware engine and high processor memory bandwidth. However, ASIC design is fixed once manufactured, which cannot afford any changes in the implemented cryptographic algorithm. FPGA implementation is attractive in terms of its re-configurability but it is generally much slower than ASIC design. In this demo, we present a novel scheme that can offload the latency of reconfigurable cryptographic engine from the overall execution and define an en-/decryption data interface, which is independent of the underlying encryption algorithms. To verify our proposed scheme, we implemented a FPGA prototype, which integrated our design with OpenRISC on ALTERA DE2i-150 evaluation board. We prove that our proposed architecture can flexibly and efficiently en-/decrypt the data with zero overheads towards overall program execution with careful design. Our case study on SQLite shows that the query execution over a 1GB encrypted database on our implemented system introduces performance overhead ranging from 0% to 14%.

Driving is an integral part of our everyday lives, but it is also a time when people are uniquely vulnerable. Previous research has demonstrated that not only does listening to suitable music while driving not impair driving performance, but it could lead to an improved mood and a more relaxed body state, which could improve driving performance and promote safe driving significantly. In this article, we propose SAfeDJ, a smartphone-based situation-aware music recommendation system, which is designed to turn driving into a safe and enjoyable experience. SAfeDJ aims at helping drivers to diminish fatigue and negative emotion. Its design is based on novel interactive methods, which enable in-car smartphones to orchestrate multiple sources of sensing data and the drivers' social context, in collaboration with cloud computing to form a seamless crowdsensing solution. This solution enables different smartphones to collaboratively recommend preferable music to drivers according to each driver's specific situations in an automated and intelligent manner. Practical experiments of SAfeDJ have proved its effectiveness in music-mood analysis, and mood-fatigue detections of drivers with reasonable computation and communication overheads on smartphones. Also, our user studies have demonstrated that SAfeDJ helps to decrease fatigue degree and negative mood degree of drivers by 49.09% and 36.35%, respectively, compared to traditional smartphone-based music player under similar driving situations.

Energy balancing is an effective technique in enhancing the lifetime of a wireless sensor network WSN. Specifically, balancing the energy consumption among sensors can prevent losing some critical sensors prematurely due to energy exhaustion so that the WSN's coverage can be maintained. However, the heterogeneous hostile operating conditions-different transmission distances, varying fading environments, and distinct residual energy levels-have made energy balancing a highly challenging task. A key issue in energy balancing is to maintain a certain level of energy fairness in the whole WSN. To achieve energy fairness, the transmission load should be allocated among sensors such that, regardless of a sensor's working conditions, no sensor node should be unfairly overburdened. In this paper, we model the transmission load assignment in WSN as a game. With our novel utility function that can capture realistic sensors' behaviors, we have derived the Nash equilibrium NE of the energy balancing game. Most importantly, under the NE, while each sensor can maximize its own payoff, the global objective of energy balancing can also be achieved. Moreover, by incorporating a penalty mechanism, the delivery rate and delay constraints imposed by the WSN application can be satisfied. Through extensive simulations, our game theoretic approach is shown to be effective in that adequate energy balancing is achieved and, consequently, network lifetime is significantly enhanced. Copyright © 2012 John Wiley & Sons, Ltd.

In the current IaaS cloud market, to achieve profit maximization, multiple cloud providers compete non-cooperatively by offering diverse price rates. At the same time, tenant consumers judiciously adjust demands accordingly, which in turn affects cloud resource prices. In this paper, we tackle this fundamental but daunting cloud price competition problem with Bertrand game modeling, and propose a dynamic game to achieve Nash equilibrium in a distributed manner. Specifically, we realistically consider spot electricity prices under a smart grid environment, and systematically investigate the impact of different system parameters such as network delay, renewable availability, and cloud resource substitutability. We also perform stability analysis to investigate the convergence of the proposed dynamic game to Nash equilibrium. Cooperation among cloud providers can achieve aggregate cloud profit maximization, but is subject to strategic manipulations. We then propose our Striker strategy to stimulate cooperation, the efficiency of which is validated by repeated game analysis. Our evaluation is augmented with realistic electricity prices in the spot energy market, and reveals insightful observations for both theoretic analysis and practical pricing scheme design.

In current IaaS cloud markets, tenant consumers non-cooperatively compete for cloud resources via demand quantities, and the service quality is offered in a best effort manner. To better exploit tenant demand correlation, cloud brokerage services provide cloud resource multiplexing so as to earn profits by receiving volume discounts from cloud providers. A fundamental but daunting problem facing a tenant consumer is competitive resource procurements via cloud brokerage. In this paper, we investigate this problem via non-cooperative game modeling. In the static game, to maximize the experienced surplus, tenants judiciously select optimal demand responses given pricing strategies of cloud brokers and complete information of the other tenants' demands. We also derive Nash equilibrium of the non-cooperative game for competitive resource procurements. Performance evaluation on Nash equilibrium reveals insightful observations for both theoretical analysis and practical cloud resource procurements scheme design.

Existing incentive schemes for peer-to-peer (P2P) file-sharing are rate-based, giving room for strategic peers to benefit from manipulative behaviors so as to treat honest peers unfairly. Specifically, strategic peers can achieve high performance by providing high upload rates which are useless to the system. On the other hand, honest peers suffer from getting low download rates even if they devote chunks with very high values which do great help to the system and other peers. In this paper, we first show that whether to upload high value chunks or low value ones in BitTorrent is a prisoners' dilemma game. We then propose a novel value-based metric, through which peers are rewarded for uploading high value chunks. We prove that by adopting the value-based metric, chunk exchange becomes a repeated game. Our simulation results indicate that our value-based approach can effectively motivate peers to contribute high value chunks to the system, which, in turn, also benefits from value-based metric by achieving a higher propagation speed of the very first copy of the file.

Thanks to years of research and development, current peer-to-peer (P2P) networks are anything but a homogeneous system from a protocol perspective. Specifically, even for the same P2P system (e.g., BitTorrent), a large number of protocol variants have been designed based on game theoretic considerations with the objective to gain performance advantages. We envision that such variants could be deployed by selfish participants and interact with the original prescribed protocol as well as among them. Consequently, a meta-strategic situation - judiciously selection of different protocol variants - will emerge. In this work, we propose a general framework, Migration, based on evolutionary game theory to study the coevolution of peers for selfish protocol selection, and, most importantly, its impact on system performance. We apply Migration to P2P systems and draw on extensive simulations to characterize the dynamics of selfish protocol selection. The revealed evolution patterns shed light on both theoretical study and practical system design.

Peer-to-peer (P2P) Mobile Ad Hoc Networks (MANETs) are widely envisioned to be a practical platform to mobile live video streaming applications (e.g., mobile IPTV). However, the performance of such a streaming solution is still largely unknown. As such, in this paper, we aim to quantify the streaming performance using a Quality of Experience (QoE) based approach. Our simulation results indicate that video streaming performance is highly sensitive to the video chunk size. Specifically, if the chunk size is small, performance, in terms of both QoE and QoS, is guaranteed but at the expense of a higher overhead. On the other hand, if chunk size is increased, performance can degrade quite rapidly. Thus, it needs some careful fine tuning of chunk size to obtain satisfactory QoE performance.

In this paper, we study the problem of discovering multiple resource holders and how to evaluate a node's satisfaction in query incentive networks. Utilizing an acyclic tree, we show that query propagation has a nature of exponential start, polynomial growth, and eventually becoming a constant. We model the query propagation as an extensive game, obtain nodes' greedy behaviors from Nash equilibrium analysis, and show the impairment of greedy behaviors via a repeated Prisoner's Dilemma. We demonstrate that cooperation enforcement is required to achieve the optimal state of resource discovery.

P2P live media streaming systems have proliferated and become indispensable vehicles for Internet based entertainment applications. However, it is also well known that scalability of such systems is limited by the lack of proper incentive mechanisms. Specifically, it is notoriously hard to efficiently allocate upload bandwidth at each peer so as to maximize overall system performance. In this paper, we propose a new auction based mechanism for optimizing the allocation of upload bandwidth at each peer. One of the distinctive features in our approach is that peers use real"goods" (i.e., their own bandwidth resources) for payments, instead of relying on some fictitious currency. Essentially, peers use a barter mechanism in the payment step in the auction. Simulation results indicate that our proposed auction approach consistently outperforms existing practical approaches (e.g., tit for tat) in terms of average incoming stream rate, average playback delay, and control packets ratio.

Energy conservation is a critical issue in the emerging standard IEEE 802.16e/m WiMAX supporting mobility. To guarantee QoS requirements in real-time services such as VoIP, traditional energy saving strategies adopt constant listen-sleep intervals, ignoring the On-Off characteristics of human speech. However, statistically the silence period can account for nearly 60% of the whole speech in time scale. Therefore, neglecting this fact can lead to unnecessary periodical listening in the silence duration, and, in turn, can result in excessive waste of battery energy. In this paper, we adopt a hybrid energy management for the downlink simplex VoIP. We also give an evaluation model to analyze the performance of the scheme. Guided by this model, we obtain the optimal window adjustment parameters. Extensive simulation results have validated the analytical model, and indicated that, compared with the traditional scheme, the hybrid scheme can achieve as much as 90% reduction in energy dissipation during silence period, while meeting the QoS requirements satisfactorily at the same time.

P2P content providers are motivated to localize traffic within Autonomous Systems and therefore alleviate the tension with ISPs stemming from costly inter-AS traffic generated by geographically distributed P2P users. In this paper, we first present a new three-tier framework to conduct a thorough study on the impact of various capacity aware or locality aware neighbor selection and chunk scheduling strategies. Specifically, we propose a novel hybrid neighbor selection strategy with the flexibility to elect neighbors based on either type of network awareness with different probabilities. We find that network awareness in terms of both capacity and locality potentially degrades system QoS as a whole and that capacity awareness faces effort-based unfairness, but enables contribution-based fairness. Extensive simulations show that hybrid neighbor selection can not only promote traffic locality but lift streaming quality and that the crux of traffic locality promotion is active overlay construction. Based on this observation, we then propose a totally decentralized network awareness protocol, equipped with hybrid neighbor selection. In realistic simulation environments, this protocol can reduce inter-AS traffic from 95% to 38% - a locality performance comparable with tracker-side strategies (35%) under the premise of high streaming quality. Our performance evaluation results provide valuable insights for both theoretical study on selfish topologies and real-deployed system design.

Multimedia streaming applications have disruptively occupied bandwidth in wire line Internet, yet today's fledging mobile media streaming still poses many challenges in efficient content distribution due to the form of mobile devices. At the same time, cloud computing is gaining power as a promising technology to transform IT industry and many eminent enterprises are developing their own cloud infrastructures. However, the lack of applications hinders clouds' large-scale implementation. In this paper, we envision a cloud-assisted power-efficient mobile P2P media streaming architecture that addresses the weakness of today's wireless access technologies. Clouds are responsible for storage and computing demanding tasks, and mobile devices colocating with each other share bandwidth and cooperatively stream media content to distribute the load. We first model interactions among mobile devices as a coalition game, and then discuss the optimal chunk retrieval scheduling. Finally, we draw on realistic mobile phone data and utilize an ARIMA model for colocation duration prediction among mobile devices.

We analyze the problem of downlink resource allocation in a non-cooperative multi-level tree topology structured wireless mesh network in which a selfish mesh router (MR) may refuse to relay other MRs' traffic so as to improve its own performance at the cost of overall system performance. Based on game theory, we propose an auction framework, where the parent MR serves as the auctioneer while its children MRs act as bidders and compete for time-slots. We derive a payment function from radio resource used for relaying traffic instead of money, so as to simplify the implementation and avoid the possible security problems from monetary payment. We prove the existence and uniqueness of Nash Equilibrium and propose a stochastic best response updating algorithm to allow the bids to iteratively converge to NE in a practical distributed fashion. Simulation results show the proposed auction algorithm greatly outperforms traditional algorithms in non-cooperative environments.

With the rapid development of wireless Internet services, several WLAN service providers may coexist in one public hotspot to compete for the same group of customers, leading to an inevitable price competition. The charged price and the provisioned packet loss at each provider are major factors in determining users' demands and behaviors, which in turn will affect providers' revenue and social welfare. In this paper, we set up a novel game model to analyze a duopoly price competition. We first show the users' demands are distributed between providers according to a Wardrop equilibrium and then prove the existence of a Nash equilibrium on providers' charged prices. Through analysis, we further find that in Nash equilibrium state the social welfare is very close to its maximal value in cooperative situation. Furthermore, the providers' aggregate revenues also do not decrease when the users have high sensitivity about the charged prices. Thus the competitive duopoly WLAN market can still run in an efficient way even in the absence of complex regulation schemes.

We study the problem of achieving proportional fair resource allocation in a non-cooperative multiuser OFDM network. We propose an auction-based scheduling algorithm, which combines the merits of the VCG auction and the greedy MC PF algorithm, to ensure that wireless users truthfully declare their resource requirements even though the users are inherently selfish. Through simulations, we find that users lying about their resource requirements are severely penalized by very high payments so that they should rather declare true valuations of subcarriers to the scheduler. Thus, the proposed auction-based scheduling algorithm can be used efficiently in a non-cooperative situation to realize proportional fairness.

In a wireless sensor network (WSN), when an adversary physically captures one or more sensor nodes, all the information stored on these nodes may be exposed completely. Consequently, the adversary can use the information to attack the remaining part of the network. In this paper, we investigate the effects of different node capture attack patterns on state-of- the-art key management schemes. We find that a compromised WSN can be made resilient to such attacks by introducing new resources, such as new nodes and new keys. Based on this observation, we propose two recovering strategies, namely, link replacement strategy and node replenishment strategy, to replace the compromised links and the functions of the compromised region, respectively. Simulation results indicate that our proposed strategies can improve the network resilience of a compromised WSN significantly with a small amount of additional resources.

Peer-to-peer (P2P) media streaming quickly emerges as an important application over the Internet. A plethora of approaches have been suggested and implemented to support P2P media streaming. In our study, we first classified existing approaches and studied their characteristics by looking at three important quantities: number of upstream peers (parents), number of downstream peers (children), and average number of links per peer. In existing approaches, peers are assigned with a fixed number of parents without regard to their contributions, measured by the amount of outgoing bandwidths. Obviously, this is an undesirable arrangement as it leads to highly inefficient use of the P2P links. This observation motivates us to model the peer selection process as a cooperative game among peers. This results in a novel peer selection protocol such that the number of upstream peers of a peer is related to its outgoing bandwidth. Specifically, peers with larger outgoing bandwidth are given more parents, which make them less vulnerable to peer dynamics. Simulation results show that the proposed protocol improves delivery ratio using similar number of links per peer, comparing with existing approaches under a wide range of system parameters.

Abstract There is a plethora of recent research on high performance wireless communications using a cross‐layer approach in that adaptive modulation and coding (AMC) schemes at wireless physical layer are used for combating time varying channel fading and enhance link throughput. However, in a wireless sensor network, transmitting packets over deep fading channel can incur excessive energy consumption due to the usage of stronger forwarding error code (FEC) or more robust modulation mode. To avoid such energy inefficient transmission, a straightforward approach is to temporarily buffer packets when the channel is in deep fading, until the channel quality recovers. Unfortunately, packet buffering may lead to communication latency and buffer overflow, which, in turn, can result in severe degradation in communication performance. Specifically, to improve the buffering approach, we need to address two challenging issues: (1) how long should we buffer the packets? and (2) how to choose the optimum channel transmission threshold above which to transmit the buffered packets? In this paper, by using discrete‐time queuing model, we analyze the effects of Rayleigh fading over AMC‐based communications in a wireless sensor network. We then analytically derive the packet delivery rate and average delay. Guided by these numerical results, we can determine the most energy‐efficient operation modes under different transmission environments. Extensive simulation results have validated the analytical results, and indicates that under these modes, we can achieve as much as 40% reduction in energy dissipation. Copyright © 2008 John Wiley & Sons, Ltd.

Due to the advancements of VLSI technologies, we can put more cores on a chip, resulting in the emergence of multi-core embedded systems. This also brings great challenges to traditional parallel processing as to how we can increase the performance of applications with increased number of cores. In this paper, we meet the challenges using a novel approach. Specifically, we propose an SoPC (System-on-Programmable-Chip) based multi-core embedded system. Under our proposed system, in addition to conventional processor cores, we introduce dynamically reconfigurable accelerator cores to boost the performance of applications. We have built a prototype of the system using FPGAs. Experimental evaluation demonstrates significant system efficiency of the proposed system in terms of computation and power consumption.

In many practical scenarios, wireless devices are autonomous and thus, may exhibit non-cooperative behaviors due to self-interests. For instance, a wireless user may report bogus channel information to gain resource allocation advantages. Such non-cooperative behaviors are practicable as the device's software could be modified by the user. In this paper, we first analyze the impact of these rationally selfish behaviors on the performance of packet scheduling algorithms in time-slotted wireless networks. Using a mixed strategy game theoretic model, we show that the traditional Maximum Rate packet scheduling algorithm can lead non-cooperative users to undesirable Nash equilibriums, in which the wireless channels are used inefficiently. By using repeated game to enforce cooperation, we further propose a novel game theoretic approach that can lead to an efficient equilibrium.

Peer-to-peer (P2P) media streaming quickly emerges as an important application over the Internet. A plethora of approaches have been suggested and implemented to support P2P media streaming. In our study, we first classified existing approaches and studied their characteristics by looking at three important quantities: number of upstream peers (parents), number of downstream peers (children) and average number of links per peer. We find that in existing approaches, peers are assigned with a fixed number of parents without regard to their contributions, measured by the amount of outgoing bandwidths. Obviously, this is an undesirable arrangement as it leads to highly inefficient use of the P2P links. This observation motivates us to model the peer selection process as a cooperative game among peers. This results in a novel peer selection protocol such that the number of upstream peers of a peer is related to its outgoing bandwidth. Specifically, peers with larger outgoing bandwidth are given more parents, which makes them less vulnerable to peer dynamics. Simulation results show that the proposed protocol improves delivery ratio with similar number of links per peer, comparing with existing approaches in a wide range of settings.

With the continued progress in VLSI technologies, we can integrate numerous cores in a single billion-transistor chip to build a multi-core system-on-a-chip (SoC). This also brings great challenges to traditional parallel programming as to how we can increase the performance of applications with increased number of cores. In this paper, we meet the challenges using a novel approach. Specifically, we propose a reconfigurable heterogeneous multi-core system. Under our proposed system, in addition to conventional processor cores, we introduce dynamically reconfigurable accelerator cores to boost the performance of applications. We have built a prototype of the system using FPGAs. Experimental evaluation demonstrates significant system efficiency of the proposed heterogeneous multi-core system in terms of computation and power consumption.

With the proliferation of sophisticated wireless devices with more than one network interfaces, it is now possible for the devices to form hybrid wireless networks. Specifically, we consider a hybrid wireless networking scenario in which each device has two heterogeneous wireless network interfaces: a server interface (e.g., a CDMA2000 cellular interface) and a peer interface (e.g., a IEEE 802.1 Ig WLAN interface). Our insight is that we could exploit the heterogeneity in energy consumption in such a dual-interface networking capability. In view of the higher energy consumption in using the server interface compared with using the client interface, we propose two novel protocols where neighboring clients form either a master-slave or peer-to-peer relationship to reduce their energy consumption. For the master-slave relationship, each master retrieves media packets from the server and sends them to its slaves via the peer interface. On the other hand, each peer-to-peer relationship consists of one coordinator and at least one helpers. Both coordinator and helpers are responsible for retrieving media packets from the server. Our analysis shows that the two proposed relationships reduce the energy consumption of participating clients. Furthermore, the relationships are stable where rational clients would not voluntarily leave and unilaterally deviate from the coalition. We evaluate their performance in homogeneous and heterogeneous client distributions. Simulation results indicate that both relationships improve streaming performance without violating the energy consumption constraints of clients.

Peer-to-peer media streaming framework has been widely considered as a promising platform for delivering high quality multimedia content on the global scale. A fundamental requirement is that each peer needs to contribute outgoing bandwidth to deliver media packets to its neighbors. Although most existing protocols mandate such contribution, misbehaving peers may still deliberately limit their outgoing bandwidth to conserve their own resources. This would inevitably lead to performance degradation of other well-behaving peers. It is crucial to have an effective incentive mechanism such that peers are encouraged to contribute. In this paper, we formulate two strategic games to model the interactions between server and its immediate peers and between neighboring peers, respectively. We have devised the equilibrium strategies which relate a peer's streaming performance to its contribution. Simulation results show that the proposed game-theoretical incentive mechanism protects well-behaving peers from being exploited by misbehaving counterparts.

Wireless peer-to-peer (P2P) file sharing is widely envisioned as one of the major applications of ad hoc networks in the near future. This trend is largely motivated by the recent advances in high-speed wireless communication technologies and high traffic demand for P2P file sharing applications. To achieve the ambitious goal of realizing a practical wireless P2P network, we need a scalable topology control protocol to solve the neighbor discovery problem and network organization problem. Indeed, we believe that the topology control mechanism should be application driven in that we should try to achieve an efficient connectivity among mobile devices in order to better serve the file sharing application. We propose a new protocol, which consists of two components, namely,adjacency set construction(ASC) andcommunity-based asynchronous wakeup(CAW). Our proposed protocol is shown to be able to enhance the fairness and provide an incentive mechanism in wireless P2P file sharing applications. It is also capable of increasing the energy efficiency.

OFDM systems are the major cellular platforms for supporting ubiquitous high performance mobile applications. However, there remain a number of research challenges to be tackled. One of the most important challenges is the design of a judicious packet scheduler so as to make efficient use of the spectrum bandwidth. In this paper, we propose a new QoS-aware proportional fairness (QPF) packet scheduling policy for the downlink of multiuser OFDM systems to allocate radio resource among users. Our proposed algorithm is based on a cross layer design in that the scheduler is aware of both channel and queue state information to achieve proportional fairness while improving each user's QoS performance. Simulation results indicate that the proposed QPF algorithm is efficient in terms of average system throughput, packet dropping probability, and packet delay, while maintaining adequate fairness among users.

Key management has long been a challenging problem in wireless distributed sensor networks (DSNs) due to their high security requirements and strict resource constraints. A randomized key pre-distribution scheme has been introduced to serve as a practical solution and many improvements are subsequently proposed. These schemes mainly focus on key allocations based on pre-deployment estimates of post-deployment information items, such as location data and attack probabilities. Unfortunately, such information items may be unavailable or may change over time. Based on adaptability to post-deployment contexts, we propose a key redistribution scheme that exploits neighboring keys from connected neighbors to reach unconnected nodes. We show that our scheme can be integrated into most existing key pre- distribution schemes to further improve their performance. We demonstrate our proposed scheme's salient features, such as high connectivity, high resilience, and efficient memory usage, by both analytical and simulation results.

Ultra wideband (UWB) systems are currently an important wireless infrastructure for efficient short- range communications. To improve the system efficiency while guaranteeing the radio link level quality of services, transmission rate and power of the mobile nodes can be dynamically adjusted by executing an optimization algorithm at the access points (APs). In this paper, we present a cross layer rate and power allocation algorithm based on the multilayer model of time hopping (TH) pulse position modulation (PPM) UWB multimedia networks. We consider the performance of the TCP protocol under the proposed cross layer allocation scheme in various realistic UWB based infrastructure networking scenarios.

The adaptive modulation and coding (AMC) schemes has long been adopted at physical layer to combat time-varying properties of the wireless channel. However, transmitting packet over deep fading channel can render extra energy expenditure, due to the incorporation of more error protection or usage of lower modulation mode, which is unaffordable for energy-limited wireless sensor device. To avoid such inefficient energy usage, a simple approach is to temporally buffer the packet when the channel is in deep fading, until the channel quality recovers. Nevertheless, buffering packet can lead to communication performance degradations - communication latency and packet overflow, which should be taken into consideration in sensing applications with QoS requirements. In this paper, by using previously proposed discrete time queuing model, we analyze the effects of Rayleigh fading on the sensor communication system, and propose a cross-layer design on power aware communication of sensor device. Specifically, in such channel adaptive system, each sensor can judiciously accesses the medium according to the channel condition, traffic load, and buffer variation. Simulation and analytical results indicate that, such cross-layer design can lead to energy conservation by as much as 30-40 per cent.

Devices in a sensor network need to work in a hostile environment and they are usually powered by batteries. Yet the whole purpose of deploying a sensor network is to perform distributed collaborative computing, possibly in a massive scale. In a hostile computing environment, the sensor devices might be routinely tampered with. Together with the possibility of faulty devices due to extreme conditions or low power, the trustworthiness of a device varies. Specifically, a device should only communicate with another device which has a trust level above a certain threshold. However, setting up trusted communication channels among sensor devices remains a major challenge. In this paper, we propose a trust-based routing scheme in sensor networks for providing a high level of robustness in node selection based on packet trust requirement with lifetime consideration. Our protocol allows messages to be routed through malicious and faulty devices with the selection of trusted neighbors. On the other hand, the network lifetime can also be prolonged by selecting those with their sensing functions covered by some existing nodes. Simulation results show that our scheme is possible to prolong the lifetime of sensor networks and maintain certain satisfactory delivery ratio.

In many practical scenarios, wireless devices are autonomous and thus, may exhibit non-cooperative behaviors due to self interests. For instance, a wireless user may report bogus channel information in order to gain resource allocation advantages. In this paper, we analyzed the impact of these rationally selfish and non-cooperative behaviors on the performance of packet scheduling algorithms in time-slotted wireless networks. Using a mixed strategy game theoretic model, we found that the traditional rate maximizing packet scheduling algorithms can lead non-cooperative devices to undesirable Nash equilibria, in which the wireless channel is used inefficiently. Motivated by this observation, we proposed a novel game theoretic scheduling approach that can lead to more efficient equilibria where all competing devices can achieve higher rates.

Key management has long been a challenging problem in wireless Distributed Sensor Networks (DSNs) due to their high security requirements and strict resource constraints. Recently, a randomized key pre-distribution scheme has been introduced to serve as a practical solution and many improvements are subsequently proposed. These schemes mainly focus on key allocations based on pre-deployment estimates of post-deployment information items, such as location data and attack probabilities. Unfortunately, such information items may be unavailable or may change over time. Based on adaptability to post-deployment contexts, we propose a general key redistribution framework that exploits neighboring keys from connected neighbors to reach unconnected nodes. We show that our framework can be applied to most existing key pre-distribution schemes (both key-based and polynomial-based) to further improve their performance. We demonstrate our proposed framework's salient features, such as high connectivity, high resilience, and efficient memory usage, by both analytical and simulation results.

Selfish behaviors of individual machines in a grid can potentially damage the performance of the system as a whole. However, scrutinizing the grid by taking into account the noncooperativeness of machines is a largely unexplored research problem. In this paper, we first present a new hierarchical game-theoretic model of the grid that matches well with the physical administrative structure in real-life situations. We then focus on the impact of selfishness in intrasite job execution mechanisms. Based on our novel utility functions, we analytically derive the Nash equilibrium and optimal strategies for the general case. To study the effects of different strategies, we have also performed extensive simulations by using a well-known practical scheduling algorithm over the NAS (numerical aerodynamic simulation) and the PSA (parameter sweep application) workloads. We have studied the overall job execution performance of the grid system under a wide range of parameters. Specifically, we find that the optimal selfish strategy significantly outperforms the Nash selfish strategy. Our performance evaluation results can serve as a valuable reference for designing appropriate strategies in a practical grid

Abstract To enhance the lifetime of a sensor network which consists of hundreds or even thousands of resource‐limited devices, energy efficient communication is mandatory. Despite that a plethora of work has been done in designing energy efficient protocols for sensor networks, the time‐varying nature of wireless channel is largely unexplored. Indeed, we believe that a cross‐layer design on power aware communication is necessary to further optimize energy usage. In this paper, we propose a new channel adaptive power aware protocol, called CAEM, which works by dynamically adjusting the data throughput under different channel conditions with the help of an adaptive channel coding and modulation facility. Each sensor device judiciously accesses the wireless medium in that communication activity is reduced for devices under poor channel conditions. Simulation results indicate that the proposed CAEM protocol can lead to energy conservation by as much as 30 per cent. Furthermore, CAEM is also efficient in channel utilization as it generates a higher data throughput even under heavy traffic load. Copyright © 2007 John Wiley & Sons, Ltd.

By utilizing massively parallel circuit design in FPGAs, the overall system efficiency, in terms of computation efficiency and energy efficiency, can be greatly enhanced by offloading some computation-intensive tasks which are originally executed in the instruction set processor to the FPGA fabric. In essence, a hardware task scheduler is needed. However, most of the work in the literature considers scheduling algorithms which are unable or difficult to be implemented using the design flows in current development platform. Moreover, little of the work takes energy consumption into consideration. In this paper, we present the design of a hardware task scheduler which takes energy consumption into consideration, and can be readily implemented using current design flows

Ultra wideband (UWB) systems are considered as the key wireless infrastructure technology for efficient short-range communications and mobile applications. In this paper, we study the problem of bandwidth scheduling in a UWB based hierarchical wireless ad hoc network, which is typically used in an enterprise-scale mobile computing environment. A novel self-organized clustering method is designed to improve system throughput. Simulation results suggest that the proposed clustering method is effective under various system configurations

We consider a wireless data access scenario where a centralized server provides data items to its clients with a fee. To reduce the total charges incurred, clients perform "peer-to-peer (P2P) sharing"—clients exchange data items at a lower cost. Specifically, P2P sharing cost is determined by two factors: energy and bandwidth. Neighboring clients share data objects among themselves if it is mutually beneficial. This would inevitably lead to reduced server's revenue. We investigate the effectiveness in using pricing as a strategy for the server to indirectly regulate the amount of P2P sharing. We propose an auction pricing mechanism that allows clients to bid for their desired data objects. Simulation results show that the proposed pricing strategy effectively deters sharing in lightly-loaded network while judiciously leverages sharing when the network is congested.

Abstract—Ultra wideband (UWB) systems are widely envisioned to be the next important wireless infrastructure for efficient short-range communications and mobile applications. Indeed, forming ad hoc networks among various UWB enabled devices is considered as an important mobile data exchange operating environment. In our study, we explore the problem of jointly optimizing the power level and data rate used in the devices in such a UWB based ad hoc network. We propose a practical optimization scheme and decompose the optimization problem into power control for real-time applications and opportunistic scheduling for non-real-time applications. Efficient optimization algorithms are designed to meet different fairness requirements and numerical results are obtained. Keywords—optimal power control, opportunistic scheduling, TH-PPM UWB, multimedia, ad hoc networks, predefined fairness, proportional fairness. 1.

Minimization of the execution time of an iterative application in a heterogeneous parallel computing environment requires an appropriate mapping scheme for matching and scheduling the subtasks of a given application onto the processors. Often, some of the characteristics of the application subtasks are unknown a priori or change from iteration to iteration during execution-time based on the inputs being processed. In such a scenario, it may not be feasible to use the same off-line-derived mapping for each iteration of the application. One possibility is to employ a semi-static methodology that starts with an initial mapping but dynamically performs remapping between application iterations by observing the effects of the changing characteristics of the application's input data, called dynamic parameters, on the application's execution time. A contribution in this paper is to implement and evaluate a semi-static methodology involving the on-line use of off-line-derived mappings. The off-line phase is based on a genetic algorithm (GA) to generate high-quality mappings for a range of values for the dynamic parameters. A dynamic parameter space partitioning and sampling scheme is proposed that partitions the parameter space into a number of hyper-rectangles, within which the “best” mapping for each hyper-rectangle is stored in a mapping table. During the on-line phase, the actual dynamic parameters are observed and the off-line-derived mapping table is referenced to choose the most suitable mapping. Experimental results indicate that the semi-static approach outperforms a dynamic on-line approach and performs reasonably close to an infeasible on-line GA approach. Furthermore, the semi-static approach considerably outperforms the method of using the same mapping for all iterations.

In scheduling a large number of user jobs for parallel execution on an open-resource grid system, the jobs are subject to system failures or delays caused by infected hardware, software vulnerability, and distrusted security policy. This paper models the risk and insecure conditions in grid job scheduling. Three risk-resilient strategies, preemptive, replication, and delay-tolerant, are developed to provide security assurance. We propose six risk-resilient scheduling algorithms to assure secure grid job execution under different risky conditions. We report the simulated grid performances of these new grid job scheduling algorithms under the NAS and PSA workloads. The relative performance is measured by the total job makespan, grid resource utilization, job failure rate, slowdown ratio, replication overhead, etc. In addition to extending from known scheduling heuristics, we developed a new space-time genetic algorithm (STGA) based on faster searching and protected chromosome formation. Our simulation results suggest that, in a wide-area grid environment, it is more resilient for the global job scheduler to tolerate some job delays instead of resorting to preemption or replication or taking a risk on unreliable resources allocated. We find that delay-tolerant min-min and STGA job scheduling have 13-23 percent higher performance than using risky or preemptive or replicated algorithms. The resource overheads for replicated job scheduling are kept at a low 15 percent. The delayed job execution is optimized with a delay factor, which is 20 percent of the total makespan. A Kiviat graph is proposed for demonstrating the quality of grid computing services. These risk-resilient job scheduling schemes can upgrade grid performance significantly at only a moderate increase in extra resources or scheduling delays in a risky grid computing environment.

We consider a basic scenario in wireless data access: a number of mobile clients are interested in a set of data items kept at a common server. Each client independently sends requests to inform the server of its desired data items and the server replies with a broadcast channel. We are interested in studying the energy consumption characteristics in such a scenario. First, we define a utility function for quantifying performance. Based on the utility function, we formulate the wireless data access scenario as a noncooperative game - wireless data access (WDA) game. Although our proposed probabilistic data access scheme does not rely on client caching, game theoretical analysis shows that clients do not always need to send requests to the server. Simulation results also indicate that our proposed scheme, compared with a simple always-request one, increases the utility and lifetime of every client while reducing the number of requests sent, with a cost of slightly larger average query delay. We also compare the performance of our proposed scheme with two popular schemes that employ client caching. Our results show that caching-only benefits clients with high query rates at the expense of both shorter lifetime and smaller utility in other clients

Selfish behaviors of individual machines in a grid can potentially damage the performance of the system as a whole. However, scrutinizing the grid by taking into account the non-cooperativeness of machines is a largely unexplored research problem. In this paper, we first present a new hierarchical game-theoretic model of the grid that matches well with the physical administrative structure in real-life situations. We then focus on the impact of selfishness in intra-site job execution mechanisms. Based on our novel utility functions, we analytically derive the Nash equilibrium and optimal strategies for the general case. To study the effects of different strategies, we have also performed extensive simulations by using a well-known practical scheduling algorithm over the NAS (Numerical Aerodynamic Simulation) workload. We have studied overall job execution performance of the grid system under a wide range of parameters. Specifically, we find that the optimal selfish strategy significantly outperforms the Nash selfish strategy. Our performance evaluation results can serve as valuable reference for designing appropriate strategies in a practical grid.

The shrew distributed denial of service (DDoS) attacks are periodic, bursty, and stealthy in nature. They are also known as reduction of quality (RoQ) attacks. Such attacks could be even more detrimental than the widely known flooding DDoS attacks because they damage the victim servers for a long time without being noticed, thereby denying new visitors to the victim servers, which are mostly e-commerce sites. Thus, in order to minimize the huge monetary losses, there is a pressing need to effectively detect such attacks in real-time. Unfortunately, effective detection of shrew attacks remains an open problem. In this paper, we meet this challenge by proposing a new signal processing approach to identifying and detecting the attacks by examining the frequency-domain characteristics of incoming traffic flows to a server. A major strength of our proposed technique is that its detection time is less than a few seconds. Furthermore, the technique entails simple software or hardware implementations, making it easily deployable in a real-life network environment.

Ubiquitous peer-to-peer (P2P) networking is widely expected to be manifested in a wireless environment in the near future. However, to realize such an interesting mobile computing platform, energy efficiency is one of the most critical resources management issues yet to be tackled. Unfortunately, energy efficient wireless P2P networking is still a relatively less explored topic as it is quite challenging to tackle the energy management problem without centralized control. In this paper, we meet this research challenge by proposing a new distributed protocol, called community-based asynchronous wakeup protocol, CAWP, for energy conservation in wireless P2P file sharing networks. Simulation results show that our proposed CAWP is found to be highly effective in that it can remarkably increase the energy efficiency of the participants in a wireless P2P system.

There have been an increasingly large number of mobile handsets equipped with dual or multiple network interfaces. The server interface (e.g., GPRS, EDGE, UMTS) is responsible for communicating with the network operator, while the peer interfaces (e.g., Bluetooth, IEEE 802.11) are used to connect with other computing devices. However, they are usually used separately. In this paper, we investigate the use of both network interfaces to support energy efficient data applications among mobile clients. Specifically, we proposed a fully distributed protocol for mobile handsets to form cooperative groups to maintain cache consistency with minimal communication with the network operator. Our proposed protocol takes advantage of the low power consumption and high data rate of the peer interface. The aim is to reduce the use of the server interface, which is typically slower and involves higher power consumption. Furthermore, we also consider the presence of selfish clients. It is shown that groups formed by the proposed protocol constitutes a pure Nash equilibrium. This suggests that our protocol is robust even in the presence of selfish clients. Simulation results confirm that, given the same energy resource, mobile clients running the proposed protocol complete more queries, experience longer lifetime and achieve smaller query latency.

Given the recent rapidly developing high speed wireless communication technologies and high traffic demand for P2P file sharing applications, wireless P2P file sharing is widely reckoned as a key component of the next generation communication network. However, running P2P applications in a wireless medium entails different constraints compared with those in the traditional wired Internet. One of the challenges is that portable wireless devices are energy-limited since they are battery-operated and the battery has inevitably limited life. Fairness and incentive are also important issues. Unfortunately, designing a protocol taking all these factors into account is still a relatively unexplored problem. We propose a topology control protocol called TCP2P for wireless P2P file sharing networks. TCP2P increases the fairness and provides incentive in wireless P2P file sharing applications and is energy-conserving.

The paper examines the following wireless data access scenario: a number of clients are interested in a set of data items kept at the server. A client sends a query request to inform the server of its desired data item. The server replies in the common broadcast channel. We first define a utility function that considers the client's power consumption in transmit, receive and idle modes. Specifically, utility is expressed as the number of queries that can be completed given a fixed energy source. Based on the utility function, we formulate our power aware wireless data access scheme as a non-cooperative game, called the WDA game. From our theoretical analysis, we show that clients are not always necessary to send query requests to the server. Instead, each client determines the request probability without any explicit communication with one another. Furthermore, we design and evaluate the server and client algorithms for the WDA game. Simulation results confirm that our proposed scheme, compared with a simple always-request one, increases the utility and lifetime of every client while reducing the number of requests sent, at the cost of a slightly larger average query delay.

To efficiently support tetherless applications in ad hoc wireless mobile computing networks, a judicious ad hoc routing protocol is needed. Much research has been done on designing ad hoc routing protocols and some well-known protocols are also being implemented in practical situations. However; one major imperfection in existing protocols is that the time-varying nature of the wireless channels among the mobile-terminals is ignored; let alone exploited. This could be a severe design drawback because the varying channel quality can lead to very poor overall route quality in turn, resulting in low data throughput. Indeed, better performance could be achieved if a routing protocol dynamically changes the routes according to the channel conditions. In this paper, we first propose two channel adaptive routing protocols which work by using an adaptive channel coding and modulation scheme that allows a mobile terminal to dynamically adjust the data throughput via changing the amount of error protection incorporated. We then present a qualitative and quantitative comparison of the two classes of ad hoc routing protocols. Extensive simulation results indicate that channel adaptive ad hoc routing protocols are more efficient in that shorter delays and higher rates are achieved, at the expense of a higher overhead in route set-up and maintenance.

Providing on-demand data access in client-server wireless networks is an important support to many interesting mobile computing applications. Caching frequently accessed data by mobile clients can conserve wireless bandwidth and battery power, at the expense of some system resources to maintain cache consistency. The basic cache consistency strategy is the use of periodic invalidation reports (IRS) broadcast by the server. Recently, IR-based approaches have been further improved by using additional updated invalidation reports (UIRs) (i.e., the IR+UIR algorithm) to reduce the long query latency. However, the performance of the IR+UIR approach in a practical system is still largely unknown. Specifically, previous results are based on two impractical simplifying assumptions: 1) broadcast traffic is error-free and 2) no other downlink traffic (e.g., voice) exists in the system. The first assumption is clearly unrealistic as signal propagation impairments (e.g., multipath fading) and, hence, packet reception failures are inevitable in a practical situation. The second assumption is also inapplicable in real life because mobile devices are usually multipurposed (e.g., a mobile phone equipped with a browser may be used for Web surfing while having a phone conversation). In this paper, we first study the performance of the IR+UIR approach under a realistic system model: The quality of the wireless channel is time-varying, and there are other downlink traffics in the system. Our simulation results show that query delay significantly increases as a result of broadcast error and the additional downlink traffics experience longer delay due to extended broadcast period. Exploiting link adaptation (i.e., transmission rate is adjusted dynamically according to channel quality), we then propose three schemes to tackle these two problems. Our results indicate that the proposed schemes outperform IR+UIR under a wide range of system parameters.

Summary form only given. Caching frequently accessed data by mobile clients can conserve wireless bandwidth and battery power, at the expense of some system resources to maintain cache consistency. The basic cache consistency strategy is the use of periodic invalidation reports (IRs) broadcast by the server. Recently, IR-based approaches have been further improved by using additional updated invalidation reports (UIRs) (i.e., the IR+UIR algorithm) to reduce the long query latency. However, the performance of the IR+UIR approach in a practical system is still largely unknown. Specifically, previous results are based on two impractical simplifying assumptions: (1) broadcast traffic is error-free; and (2) no other downlink traffic (e.g., voice) exists in the system. The first assumption is clearly unrealistic as signal propagation impairments (e.g., multipath fading), and hence, packet reception failures, are inevitable in a practical situation. The second assumption is also inapplicable in real life because mobile devices are usually multipurposed (e.g., a mobile phone equipped with a browser may be used for Web-surfing while having a phone conversation). We first study the performance of the IR+UIR approach under a realistic system model: the quality of the wireless channel is time-varying; and there are other downlink traffics in the system. Our simulation results show that query delay significantly increases as a result of broadcast error and the additional downlink traffics experience longer delay due to extended broadcast period. Exploiting link adaptation (i.e., transmission rate is adjusted dynamically according to channel quality), we then propose three schemes to tackle these two problems.

Short-range wireless technologies are becoming increasingly important in enabling useful mobile applications. Bluetooth and IEEE 802.11b standards are the most commonly deployed technologies for WPAN and WLAN. However, because both standards share the same unlicensed ISM (Industrial, Scientific, Medical) radio spectrum, severe interference is inevitable and performance can be impaired significantly when heterogeneous devices using the two technologies come into close proximity. The most notable solution to this problem is a frequency domain noncollaborative coexistence mechanism called adaptive frequency hopping (AFH). However, we find that the efficiency of the "channel classification" sub-process in noncollaborative mechanisms is by and large ignored in the literature. Moreover, we also find that there is no system resources awareness and no interference source genre concerns in IEEE 802.15 Task Group 2 AFH (TG2 AFH) design. Thus, we suggest a new approach called ISOAFH (Interference Source Oriented AFH). With the above considerations, we propose a customized channel classification process, thereby simplifying the time and space complexity of the mechanism. Through our detailed implementation of various coexistence mechanisms in MATLAB Simulink, it is observed that TG2 AFH performance is sensitive to memory and power limitations, while ISOAFH is much less sensitive to these constraints and can keep a much lower channel collision rate. On the other hand, We also study some open issues of a time domain mechanism called MDMS (Master Delay MAC Scheduling). We compare different coexistence mechanisms and find that the performance of each approach very much depends on the efficiency of its sub-processes.

Scatternet management remains to be one of the most crucial research issues for Bluetooth networks, despite that Bluetooth devices have proliferated in the commercial market. In this paper, we describe our proposed integrated scheme for effective scatternet management. Our proposed scheme contains four main mechanisms to address the different facets of the problem, namely compensation-based time-slot assignment (CTSA), traffic differentiation queueing (TDQ), adaptive master-slave switching (AMSS), and an enhanced AODV algorithm for ad hoc routing. We have built a comprehensive Bluetooth simulator and performed extensive simulations to evaluate the proposed IARTSS. We find that our proposed scheme can perform well under a wide variety of practical circumstances, and provides efficient and high performance intra-piconet and inter-piconet communications.

Ad hoc routing is important for mobile devices, when they are out of each others transmission range, to communicate in an IEEE 802.11b based wireless LAN using the distributed coordination function. While traditional table-based or on-demand routing protocols can be used, it is much more efficient to use a routing protocol that is channel-adaptive - judiciously selecting links that can transmit at higher data rates to form a route. However, devising channel-adaptive routing protocols is still largely unexplored. In this paper, we propose a reactive ad hoc routing algorithm, called RICA (receiver-initiated channel-adaptive) protocol, to intelligently utilize the multi-rate services (based on different modulation schemes) provided by the IEEE 802.11b standard. Our NS-2 simulation results show that the RICA protocol is highly effective.

As wireless LAN (WLAN) technologies proliferate, it is becoming common that ad hoc networks, in which mobile devices communicate via temporary links, are built using WLAN products. In the IEEE 802.11b standard, the wired equivalent privacy (WEP) scheme is used as the only measure to enhance data confidentiality against eavesdropping. However, owing to well known pitfalls in initialization vector (IV) attachment in the ciphertext, the underlying 40-bit RC4 encryption mechanism in WEP is unsafe regardless of the key size. On the other hand, solutions involving replacement of RC4 by another cipher are not attractive because that may lead to reconstruction of the whole system and result in high cost as well as redevelopment of the products. In order to enhance the security on the existing development efforts, we propose a novel multipath routing approach to combat the link insecurity problem at a higher protocol layer. This approach does not require the application to use sophisticated encryption technologies that may be too heavy burdens for mobile devices. Based on our suggested confidentiality measurement model, we find that our proposed multipath ad hoc routing technique called secure multipath source routing (SMSR), is highly effective.

Multiple access control (MAC) of the uplink in a wireless mobile computing system is one of the most important resource allocation problems in that the response time and throughput of user applications (e.g., wireless web surfing) are critically affected by the efficiency of the MAC protocol. Compared with a traditional MAC problem (e.g., wireline Ethernet), there are two important new challenges in a modern wireless network: (1) multimedia data with diverse traffic requirements are involved; and (2) the wireless channel has a time-varying quality for each user. Furthermore, a more prominent user requirement is fairness among different users, possibly, with different traffic demands. While some protocols have been suggested to handle multimedia data and/or tackling the time-varying channel, there are a number of drawbacks in these existing protocols. The most notable drawback is that the channel model is rather unrealistic - just using a two state Markov chain instead of relying on accurate models of multipath fading and shadowing effects. Another common deficiency is that fairness is ignored. In this paper, we propose to use a new notion of fairness that can capture a realistic channel model, and to integrate a fair queuing scheduling algorithm in a MAC protocol to optimize performance while maintaining fairness among users regardless of their channel states and data types.

We propose an enhancement to the original MAC (multiple access control) protocol in the IEEE 802.11 standard by improving the handshake mechanism and adding one more separate power control channel. With the control channel, the receiver notifies its neighbors about the noise tolerance. Thus, the neighbors can adjust their transmission power levels to avoid packet collision at the receiver. Through extensive simulations on the NS-2 platform, our power control mechanism is found to be effective in that network throughput can be increased by about 10%.

In packet radio networks, especially an ad hoc wireless network using IEEE 802.11 as the MAC (media access control) protocol, power control is a crucial issue. By using a judicious power control mechanism, co-channel interference can be significantly reduced, thus improving the channel spatial reuse and network capacity. However, efficient power control in an IEEE 802.11 system is very challenging because according to the standard, fixed power is used for transmitting packets, and there is only one channel. In this paper, we propose an enhancement to the standard IEEE 802.11 MAC protocol by improving the handshaking mechanisms and adding one separate power control channel. With the control channel, the receiver notifies its neighbors its noise tolerance. Thus, the neighbors can adjust their transmission power levels to avoid packet collisions at the receiver. Through extensive simulations using NS-2, our proposed power control mechanism is found to be effective in that network throughput can be increased by about 10%, and the battery utilization can also be improved at the same time.

This study proposes an integrated ad hoc routing and time-slot scheduling (IARTSS) scheme to address the problem of ad hoc routing in Bluetooth networks. Our proposed scheme contains four main mechanisms to address the different facets of the problem, namely compensation- based time-slot assignment (CTSA), traffic differentiation queueing (TDQ), adaptive master-slave switching (AMSS), and an enhanced AODV algorithm for ad hoc routing. CTSA judiciously allocates time slots to slaves based on elapsed time, utilization, and queue lengths, helping the bridge nodes to catch up with the lagging of services in piconets. TDQ differentiates traffic into self-originated and forwarded messages, and serves them in a dynamically adjusted adaptive ratio. AMSS calculates the time for a bridge node to stay in a piconet in a more effective way, based on utilization fraction and queue lengths. Enhanced AODV for ad hoc routing is implemented as a routing protocol for Bluetooth scatternet. We have built a comprehensive Bluetooth simulator and performed extensive simulations to evaluate the proposed IARTSS. We find that our proposed scheme can perform well under a wide variety of practical circumstances, and provides efficient and high performance intra-piconet and inter-piconet communications.

CDMA (code division multiple access) systems are critical building blocks of future high performance wireless and mobile computing systems. While CDMA systems are very mature for voice services, their potentials in delivering high quality data services are yet to be investigated. One of the most crucial component in an advanced wideband CDMA system is the judicious allocation of bandwidth resources to both voice and high data rate services so as to maximize utilization while satisfying the respective quality of service requirements. Specifically, in a multicode CDMA system, the problem is to intelligently allocate codes to the users' requests. While previous work in the literature has addressed this problem from a capacity point of view, the fairness aspect, which is also important from the users' point of view, is largely ignored. In this paper, we propose a new code allocation approach that is channel adaptive and can guarantee fairness with respect to the users' channel conditions. Simulation results show that out approach is more effective than the proportional fair approach.

To fully exploit the potential of a wideband CDMA-based mobile Internet computing system, an efficient algorithm is needed for judiciously performing rate allocation, so as to orchestrate and allocate bandwidth for voice services and high data rate applications. However, in existing standards (e.g., cdma2000), only a first-come-first-served equal sharing allocation algorithm is used, potentially leading to a low bandwidth utilization and inadequate support of high data rate multimedia mobile applications (e.g., video/audio files swapping, multimedia messaging services, etc.). In this paper, we first analytically model the rate allocation problem that captures realistic system constraints such as downlink power limits and control, uplink interference effects, physical channel adaptation, and soft handoff. We then suggest six efficient rate allocation schemes that are designed based on different philosophies: rate optimal, fairness-based, and user-oriented. Simulations are performed to evaluate the effectiveness of the rate allocation schemes using realistic system parameters in our model.

In a code-division multiple access (CDMA)-based wireless communication system, forward link is power limited and reverse link is interference limited. With power control and statistical multiplexing, voice services can be supported reasonably well. However, for high data-rate services, a more comprehensive scheduling mechanism is needed in order to achieve a high capacity while satisfying the forward and reverse link constraints. We formulate the high data-burst scheduling as a integer programming problem using a generic CDMA system model. We also suggest an optimal algorithm for generating scheduling solutions. With cdma2000 system details plugged in the proposed algorithm, it is found that our algorithm considerably outperforms several fast heuristics, including equal sharing, first-come-first-served, longest delay first, and shortest burst first.

Wireless fair queueing algorithms have been extensively studied recently. However, a major drawback in existing approaches is that the channel model is overly simplified - a two states (good or bad) channel is assumed. While it is relatively easy to analyze the system using such a simple model, the algorithms so designed are of a limited applicability in a practical environment, in which the level of burst errors are time-varying and can be exploited by using channel adaptive coding and modulation techniques. In this paper, we first argue that the existing algorithms cannot cater for a more realistic channel model and the traditional notion of fairness is not suitable. We then propose a new notion of fairness, which bounds the actual throughput normalized by channel capacity of any two sessions. Using the new fairness definition, we propose a new fair queueing algorithm called CAFQ (channel adaptive fair queueing), which, as indicated in our numerical studies, outperforms other algorithms in terms of overall system throughput and fairness among error prone sessions.

To support truly peer-to-peer applications in ad hoc wireless mobile computing networks, a judicious and efficient ad hoc routing protocol is needed. Much research has been done on designing ad hoc routing protocols and some well known protocols are also being implemented in practical situations. However, one major drawback in existing state-of-the-art protocols, such as the AODV routing protocol, is that the time-varying nature of the wireless channels among the mobile terminals is ignored, let alone exploited. This can be a severe design shortcoming because the varying channel quality can lead to very poor overall route quality, in turn result in low data throughput. In this paper, by using a previously proposed adaptive channel coding and modulation scheme which allows a mobile terminal to dynamically adjust the data throughput via changing the amount of error protection incorporated, we devise a new receiver-initiated algorithm for ad hoc routing that dynamically changes the routes according to the channel conditions. Extensive simulation results indicate that our proposed protocol are more efficient in that shorter delays and higher rates are achieved.

To support truly peer-to-peer applications in ad hoc wireless networks, a judicious and efficient ad hoc routing protocol is needed. Much research has been done on designing ad hoc routing protocols and some well known protocols are also being implemented in practical situations. However, one major drawback in existing state-of-the-art protocols, such as the AODV (ad hoc on demand distance vector) routing protocol, is that the time-varying nature of the wireless channels among the mobile terminals is ignored, let alone exploited. In this paper, by using a previously proposed adaptive channel coding and modulation scheme which allows a mobile terminal to dynamically adjust the data throughput via changing the amount of error protection incorporated, we devise a new ad hoc routing algorithm that dynamically changes the routes according to the channel conditions. Extensive simulation results indicate that our proposed protocol is more efficient in that shorter delays and higher rates are achieved.

Multiagent computing on a cluster of workstations is widely envisioned to be a powerful paradigm for building useful distributed applications. The agents of the system span across all the machines of a cluster. Just like the case of traditional distributed systems, load balancing becomes an area of concern. With different characteristics between ordinary processes and agents, it is both interesting and useful to investigate whether conventional load-balancing strategies are also applicable and sufficient to cope with the newly emerging needs, such as coping with temporally continuous agents, devising a performance metric for multiagent systems, and taking into account the vast amount of communication and interaction among agent. This paper discusses the above issues with reference to agent properties and load balancing techniques and outlines the space of load-balancing design choices in the arena of multiagent computing. In view of the special agent characteristics, a novel communication-based load-balancing algorithm is proposed, implemented, and evaluated. The proposed algorithm works by associating a credit value with each agent. The credit of an agent depends on its affinity to a machine, its current workload, its communication behavior, and mobility, etc. When a load imbalance occurs, the credits of all agents are examined and an agent with a lower credit value is migrated to relatively lightly loaded machine in the system. Quasi-simulated experiments of this algorithm show load-balancing improvement compared with conventional workload-oriented load-balancing schemes.

We consider the uplink access control problem in a mobile nomadic computing system, which is based on a cellular phone network in that a user can use the mobile device to transmit voice or file data. This resource management problem is important because an efficient solution to uplink access control is critical for supporting a large user population with a reasonable level of quality of service (QoS). While there are a number of recently proposed protocols for uplink access control, these protocols possess a common drawback in that they do not adapt well to the burst error properties, which are inevitable in using wireless communication channels. We propose a novel TDMA-based uplink access protocol, which employs a channel state dependent allocation strategy. Our protocol is motivated by two observations: (1) when channel state is bad, the throughput is low due to the large amount of FEC (forward error correction) or excessive ARQ (automatic repeated request) that is needed and (2) because of item 1, much of the mobile device's energy is wasted. The proposed protocol works closely with the underlying physical layer in that, through observing the channel state information (CSI) of each mobile device, the MAC protocol first segregates a set of users with good CSI from requests gathered in the request contention phase of an uplink frame. The protocol then judiciously allocates channel bandwidth to contending users based on their channel conditions. Simulation results indicate that the proposed protocol considerably outperforms five state-of-the-art protocols in terms of packet loss, delay, and throughput.

Several load balancing schemes have been proposed for distributed object computing systems, which are widely envisioned to be the desired distributed software development paradigm due to the higher modularity and the capability of handling machine and operating system heterogeneity. However, while the rationales and mechanisms employed are dramatically different, the relative strengths and weaknesses of these approaches are unknown, making it difficult for a practitioner to choose an appropriate approach for the problem at hand. In this paper, we describe in detail three representative approaches, which are all practicable, and present a quantitative comparison using our experimental distributed object computing platform. Among these three approaches, namely, JavaSpaces based, request redirection based, and fuzzy decision based, we find that the fuzzy decision based algorithm outperforms the other two considerably.

3rd generation mobile systems are mostly based on the wideband CDMA platform to support high bit rate packet data services. One important component to offer packet data service in CDMA is a burst admission control algorithm. In this paper, we propose and study a novel jointly adaptive burst admission algorithm, namely the jointly adaptive burst admission-spatial dimension algorithm (JABA-SD) to effectively allocate valuable resources in wideband CDMA systems to burst requests. In the physical layer, we have a variable rate channel-adaptive modulation and coding system which offers variable throughput depending on the instantaneous channel condition. In the MAC layer, we have an optimal multiple-burst admission algorithm. We demonstrate that synergy could be attained by interactions between the adaptive physical layer and the burst admission layer. We formulate the problem as an integer programming problem and derive an optimal scheduling policy for the jointly adaptive design. Both the forward link and the reverse link burst requests are considered and the system is evaluated by dynamic simulations which takes into account of the user mobility, power control and soft-handoff. We found that significant performance improvement, in terms of average packet delay, data user capacity and coverage, could be achieved by our scheme compared to the existing burst assignment algorithms.

On the verge of realizing truly ubiquitous access to high quality data (e.g., media, financial, etc.), an efficient burst admission control algorithm is crucial in third generation (3G) wireless communication systems based on wideband CDMA standards. In this paper, we propose and analyze the performance of a novel burst admission technique, called the multiple- burst admission-spatial dimension algorithm (MBA-SD) to judiciously allocate the precious channels in wideband CDMA systems to burst requests. The major contributions of the present paper are the novel formulation of the problem as an integer programming problem and the derivation of an optimal algorithm for scheduling the burst requests. Both the forward link and the reverse link burst requests are considered and the system is simulated by dynamic simulations which takes into account of the user mobility, power control, and soft hand-off. We found that significant performance improvement, in terms of data user capacity coverage, and admission and outage probabilities, could be achieved by our scheme compared to the existing burst assignment algorithms.

In our previous study, we have formulated the burst admission control problem for wideband CDMA systems as an integer programming problem. In this paper, we propose and analyze the performance of a novel burst admission technique, called the multiple-burst admission-spatial dimension algorithm (MBA-SD) to judiciously allocate the previous channels in wideband CDMA systems to burst requests. Both the forward link and the reverse link burst requests are considered and the system is simulated by dynamic simulations which takes into account the user mobility, power control and soft hand-off. We found that significant performance improvement, in terms of data user capacity, coverage, and admission and outage probabilities, could be achieved by our scheme compared to the existing burst assignment algorithms.

The multiple access control (MAC) problem in a wireless network has intrigued researchers for years. For a broadband wireless multimedia network such as wireless ATM, an effective MAC protocol is very much desired because efficient allocation of channel bandwidth is imperative in accommodating a large user population with satisfactory quality of service. Indeed, MAC protocols for a wireless ATM network, in which user traffic requirements are highly heterogeneous (classified into CBR, VBR, and ABR), are even more intricate to design. Considerable research efforts expended in tackling the problem have resulted in a myriad of MAC protocols. While each protocol is individually shown to be effective by the respective designers, it is unclear how these different protocols compare against each other on a unified basis. We quantitatively compare seven previously proposed TDMA-based MAC protocols for integrated wireless data and voice services. We first propose a taxonomy of TDMA-based protocols, from which we carefully select seven protocols, namely SCAMA, DTDMA/VR, DTDMA/PR, D4RUMA, DPRMA, DSA++, and PRMA/DA, such that they are devised based on rather orthogonal design philosophies. The objective of our comparison is to highlight the merits and demerits of different protocol designs.

We consider the uplink access control problem in a mobile computing system, which is based on a cellular phone network in that a user can use the mobile device to transmit voice or file data. This resource management problem is important because efficient solution to uplink access control is critical for supporting a large user population with a reasonable level of quality of service (QoS). While there are a number of recently proposed protocols for uplink access control, these protocols possess a common drawback in that they do not exploit well the burst error properties, which are inevitable in a wireless communication system. In this paper, we propose a novel TDMA-based uplink access protocol, which employs a channel state dependent allocation strategy. Our protocol is motivated by two observations: (1) when channel state is bad, the throughput is low due to large amount of FEC (forward error correction) or excessive ARQ (automatic repeated request) is needed; and (2) because of (1), much of the mobile device's energy is wasted. The proposed protocol works closely with the underlying physical layer in that through observing the channel state information (CSI) of each mobile user, the MAC protocol first segregates a set of users with good CSI from requests gathered in the request contention phase of an uplink frame. The protocol then judiciously allocates channel bandwidth to contending users based on their channel conditions. Simulation results indicate that the proposed protocol considerably outperforms five state-of-the-art protocols in terms of packet loss, delay, and throughput.

In this paper, we propose a new multiple access control (MAC) protocol for wireless distributed multimedia systems based on ATM, in which user demands are highly heterogeneous and can be classified as CBR, VBR, and ABR. Our protocol is motivated by two of the most significant drawbacks of existing protocols: (1) channel condition is ignored or not exploited, and (2) inflexible or biased time slots allocation algorithms are used. Indeed, existing protocols mostly ignore the burst errors due to fading and shadowing, which are inevitable in a mobile and wireless communication environment. A few protocols take into account the burst errors but just “handle” the errors in a passive manner. On the other hand, most of the existing protocols employ an inflexible or biased allocation algorithm such that over-provisioning may occur for a certain class of users at the expense of the poor service quality received by other users. Our proposed protocol, called SCAMA (synergistic channel adaptive multiple access), does not have these two drawbacks. The proposed protocol works closely with the underlying physical layer in that through observing the channel state information (CSI) of each mobile user, the MAC protocol first segregates a set of users with good CSI from requests gathered in the request contention phase of an uplink frame. The MAC protocol then judiciously allocates information time slots to the users according to their traffic types, CSI, urgency, and throughput, which are collectively represented by a novel and flexible priority function.

The multiple access control (MAC) problem in a wireless network has intrigued researchers for years. An effective MAC protocol is very much desired because efficient allocation of channel bandwidth is imperative in accommodating a large user population with satisfactory quality of service. MAC protocols for integrated data and voice services in a cellular wireless network are even more intricate to design due to the dynamic user population size and traffic demands. Considerable research efforts expended in tackling the problem have resulted in a myriad of MAC protocols. While each protocol is individually shown to be effective by the respective designers, it is unclear how these different protocols compare against each other on a unified basis. In this paper, we quantitatively compare six recently proposed TDMA-based MAC protocols for integrated wireless data and voice services. We first propose a taxonomy of TDMA-based protocols, from which we carefully select six protocols, namely CHARISMA, D-TDMA/VR, D-TDMA/FR, DRMA, RAMA, and RMAV, such that they are devised based on rather orthogonal design philosophies. The objective of our comparison is to highlight the merits and demerits of different protocol designs.

We introduce a novel multiple access control (MAC) protocol for integrated wireless voice and data services on the uplink channel in a cellular wireless network. The proposed protocol is TDMA based and the uplink frame is divided into two subframes: a request subframe and an information subframe. Our scheme, called CHARISMA (Channel Adaptive Reservation-based Isochronous Multiple Access), works by first gathering users' request via the mini-slots in the request subframe and then decides on the allocation of the information slots in the information subframe based on the channel states ranking of the mobile users. Our extensive simulation results indicate that significant improvements in terms of throughput, delay, and packet loss probability are achieved using the CHARISMA protocol.

In this paper, we consider the problem of scheduling and mapping precedence-constrained tasks to a network of heterogeneous processors. In such systems, processors are usually physically distributed, implying that the communication cost is considerably higher than in tightly coupled multiprocessors. Therefore, scheduling and mapping algorithms for such systems must schedule the tasks as well as the communication traffic by treating both the processors and communication links as important resources. We propose an algorithm that achieves these objectives and adapts its tasks scheduling and mapping decisions according to the given network topology. Just like tasks, messages are also scheduled and mapped to suitable links during the minimization of the finish times of tasks. Heterogeneity of processors is exploited by scheduling critical tasks to the fastest processors. Our extensive experimental study has demonstrated that the proposed algorithm is efficient, robust, and yields consistent performance over a wide range of scheduling parameters.

Existing heuristics for scheduling a node and edge weighted directed task graph to multiple processors can produce satisfactory solutions but incur high time complexities, which tend to exacerbate in more realistic environments with relaxed assumptions. Consequently, these heuristics do not scale well and cannot handle problems of moderate sizes. A natural approach to reducing complexity, while aiming for a similar or potentially better solution, is to parallelize the scheduling algorithm. This can be done by partitioning the task graphs and concurrently generating partial schedules for the partitioned parts, which are then concatenated to obtain the final schedule. The problem, however, is nontrivial as there exists dependencies among the nodes of a task graph which must be preserved for generating a valid schedule. Moreover, the time clock for scheduling is global for all the processors (that are executing the parallel scheduling algorithm), making the inherent parallelism invisible. In this paper, we introduce a parallel algorithm that is guided by a systematic partitioning of the task graph to perform scheduling using multiple processors. The algorithm schedules both the tasks and messages, and is suitable for graphs with arbitrary computation and communication costs, and is applicable to systems with arbitrary network topologies using homogeneous or heterogeneous processors. We have implemented the algorithm on the Intel Paragon and compared it with three closely related algorithms. The experimental results indicate that our algorithm yields higher quality solutions while using an order of magnitude smaller scheduling times. The algorithm also exhibits an interesting trade-off between the solution quality and speedup while scaling well with the problem size.

In the area of parallelizing compilers, considerable research has been carried out on data dependency analysis, parallelism extraction, as well as program and data partitioning. However, designing a practical, low complexity scheduling algorithm without sacrificing performance remains a challenging problem. A variety of heuristics have been proposed to generate efficient solutions but they take prohibitively long execution times for moderate size or large problems. In this paper, we propose an algorithm called FASTEST (Fast Assignment and Scheduling of Tasks using an Efficient Search Technique) that has O(e) time complexity, where e is the number of edges in the task graph. The algorithm first generates an initial solution in a short time and then refines it by using a simple but robust random neighborhood search. We have also parallelized the search to further lower the time complexity. We are using the algorithm in a prototype automatic parallelization and scheduling tool which compiles sequential code and generates parallel code optimized with judicious scheduling. The proposed algorithm is evaluated with several application programs and outperforms a number of previous algorithms by generating parallelized code with shorter execution times, while taking dramatically shorter scheduling times. The FASTEST algorithm generates optimal solutions for a majority of the test cases and close-to-optimal solutions for the rest.

Obtaining an optimal schedule for a set of precedence-constrained tasks with arbitrary costs is a well-known NP-complete problem. However, optimal solutions are desired in many situations. In this paper we propose search-based algorithms for determining optimal schedules for moderately large problem sizes. The first algorithm which is based on the A* search technique uses a computationally efficient cost function for guiding the search with reduced complexity. We propose a number of state-pruning techniques to reduce the size of the search space. For further lowering the complexity, we parallelize the search. The parallel version is based on reduced interprocessor communication and is guided by static and dynamic load-balancing schemes to evenly distribute the search states to the processors. We also propose an approximate algorithm that guarantees a bounded deviation from the optimal solution but takes considerably shorter time. Based on an extensive experimental evaluation of the algorithms, we conclude that the parallel algorithm with pruning techniques is an efficient scheme for generating optimal solutions for medium to moderately large problems while the approximate algorithm is a useful alternative if slightly degraded solutions are acceptable.

One of the main obstacles in obtaining high performance from message-passing multicomputer systems is the inevitable communication overhead which is incurred when tasks executing on different processors exchange data. Given a task graph, duplication-based scheduling can mitigate this overhead by allocating some of the tasks redundantly on more than one processor. In this paper, we focus on the problem of using duplication in static scheduling of task graphs on parallel and distributed systems. We discuss five previously proposed algorithms and examine their merits and demerits. We describe some of the essential principles for exploiting duplication in a more useful manner and, based on these principles, propose an algorithm which outperforms the previous algorithms. The proposed algorithm generates optimal solutions for a number of task graphs. The algorithm assumes an unbounded number of processors. For scheduling on a bounded number of processors, we propose a second algorithm which controls the degree of duplication according to the number of available processors. The proposed algorithms are analytically and experimentally evaluated and are also compared with the previous 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.

A major cost in retrieving multimedia data from multiple sites is the cost incurred in transferring multimedia data objects (MDOs) from different sites to the site where the query is initiated. The objective of a data allocation algorithm is to locate the MDOs at different sites so as to minimize the total data transfer cost incurred in executing a given set of queries. The optimal allocation of MDOs depends on the query execution strategy employed by a distributed multimedia system while the query execution strategy optimizes a query based on this allocation. We fix the query execution strategy and develop a site-independent MDO dependency graph representation to model the dependencies among the MDOs accessed by a query. Given the MDO dependency graphs as well as the set of multimedia database sites, data transfer costs between the sites, the allocation limit on the number of MDOs that can be allocated at a site, and the query execution frequencies from the sites, an allocation scheme is generated. We formulate the data allocation problem as an optimization problem. We solve this problem with a number of techniques that broadly belong to three classes: max-flow min-cut, state-space search, and graph partitioning heuristics. The max-flow min-cut technique formulates the data allocation problem as a network-flow problem, and uses a hill-climbing approach to try to find the optimal solution. For the state-space search approach, the problem is solved using a best-first search algorithm. The graph partitioning approach uses two clustering heuristics, the agglomerative clustering and divisive clustering. We evaluate and compare these approaches, and assess their cost-performance trade-offs. All algorithms are also compared with optimal solutions obtained through exhaustive search. Conclusions are also made on the suitability of these approaches to different scenarios.

In this paper, we propose a static scheduling algorithm for allocating task graphs to fully connected multiprocessors. We discuss six recently reported scheduling algorithms and show that they possess one drawback or the other which can lead to poor performance. The proposed algorithm, which is called the Dynamic Critical-Path (DCP) scheduling algorithm, is different from the previously proposed algorithms in a number of ways. First, it determines the critical path of the task graph and selects the next node to be scheduled in a dynamic fashion. Second, it rearranges the schedule on each processor dynamically in the sense that the positions of the nodes in the partial schedules are not fixed until all nodes have been considered. Third, it selects a suitable processor for a node by looking ahead the potential start times of the remaining nodes on that processor, and schedules relatively less important nodes to the processors already in use. A global as well as a pair-wise comparison is carried out for all seven algorithms under various scheduling conditions. The DCP algorithm outperforms the previous algorithms by a considerable margin. Despite having a number of new features, the DCP algorithm has admissible time complexity, is economical in terms of the number of processors used and is suitable for a wide range of graph structures.

In this paper, we explore the problem of scheduling parallel programs using task duplication for message-passing multicomputers. Task duplication means scheduling a parallel program by redundantly executing some of the tasks on which other tasks of the program critically depend. This can reduce the start times of tasks waiting for messages from tasks residing in other processors. There have been a few scheduling algorithms using task duplication. We discuss two such previously reported algorithms and describe their differences, limitations and suitability for different environments. A new algorithm is proposed which outperforms both of these algorithms, and is more efficient for low as well as high values of communication-to-computation ratios. The algorithm takes into account arbitrary computation and communication costs. All three algorithms are tested by scheduling some of the commonly encountered graph structures.

An algorithm for compile-time static scheduling of task graphs onto multiprocessors is proposed. The proposed algorithm, which is called Dynamic Critical Path (DCP) scheduling algorithm, is different from previously reported algorithms in a number of ways. First, it determines the critical path of the task graph and selects the next node to be scheduled in a dynamic fashion. Second, it rearranges the schedule on each processor dynamically in the sense that the positions of the nodes in the partial schedules are not fixed until all nodes have been considered. Third, it uses an intelligent way to select a suitable processor for a node by looking ahead the potential start times of the remaining critical nodes on that processor and by scheduling relatively less important nodes to the processors already in use. Four related scheduling algorithms are also discussed. Although these algorithms are efficient in general, they possess drawbacks which can lead to poor performance. The proposed DCP algorithm overcomes the drawbacks of these algorithms and outperforms them by a considerable margin. Despite having a number of new features, the DCP algorithm is fast, efficient in terms of the number of processors used and is equally suitable for different types of graph structures.