A 1-Local Asymptotic 13/9-Competitive Algorithm for Multicoloring Hexagonal Graphs

In the frequency allocation problem, we are given a mobile telephone network, whose geographical coverage area is divided into cells, wherein phone calls are serviced by assigning frequencies to them so that no two calls emanating from the same or neighboring cells are assigned the same frequency. The problem is to use the frequencies efficiently, i.e., minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph. In this paper, we give a 1-local asymptotic 4/3-competitive distributed algorithm for multicoloring a triangle-free hexagonal graph, which is a special case of hexagonal graph. Based on this result, we then propose a 1-local asymptotic13/9-competitive algorithm for multicoloring the (general-case) hexagonal graph, thereby improving the previous 1-local 3/2-competitive algorithm. A preliminary version of this paper appeared in the Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON 2007), LNCS 4598, pp. 526–536. Y. Zhang research was supported by European Regional Development Fund (ERDF). F.Y.L. Chin research was supported by Hong Kong RGC Grant HKU-7113/07E. H. Zhu research was supported by National Natural Science Fund (grant #60496321).     

Graph OLAP: a multi-dimensional framework for graph data analysis

Databases and data warehouse systems have been evolving from handling normalized spreadsheets stored in relational databases, to managing and analyzing diverse application-oriented data with complex interconnecting structures. Responding to this emerging trend, graphs have been growing rapidly and showing their critical importance in many applications, such as the analysis of XML, social networks, Web, biological data, multimedia data and spatiotemporal data. Can we extend useful functions of databases and data warehouse systems to handle graph structured data? In particular, OLAP (On-Line Analytical Processing) has been a popular tool for fast and user-friendly multi-dimensional analysis of data warehouses. Can we OLAP graphs? Unfortunately, to our best knowledge, there are no OLAP tools available that can interactively view and analyze graph data from different perspectives and with multiple granularities. In this paper, we argue that it is critically important to OLAP graph structured data and propose a novel Graph OLAP framework. According to this framework, given a graph dataset with its nodes and edges associated with respective attributes, a multi-dimensional model can be built to enable efficient on-line analytical processing so that any portions of the graphs can be generalized/specialized dynamically, offering multiple, versatile views of the data. The contributions of this work are three-fold. First, starting from basic definitions, i.e., what are dimensions and measures in the Graph OLAP scenario, we develop a conceptual framework for data cubes on graphs. We also look into different semantics of OLAP operations, and classify the framework into two major subcases: informational OLAP and topological OLAP. Second, we show how a graph cube can be materialized by calculating a special kind of measure called aggregated graph and how to implement it efficiently. This includes both full materialization and partial materialization where constraints are enforced to obtain an iceberg cube. As we can see, due to the increased structural complexity of data, aggregated graphs that depend on the underlying “network” properties of the graph dataset are much harder to compute than their traditional OLAP counterparts. Third, to provide more flexible, interesting and informative OLAP of graphs, we further propose a discovery-driven multi-dimensional analysis model to ensure that OLAP is performed in an intelligent manner, guided by expert rules and knowledge discovery processes. We outline such a framework and discuss some challenging research issues for discovery-driven Graph OLAP.     

一种基于分层率失真优化的容错性视频转码算法

容错性视频转码能够在已压缩视频流中嵌入容错性工具,以增强视频流面向无线信道的抗误码能力.但是容错性工具的嵌入在降低失真的同时也会增加码率,因此需要进行率失真优化.针对这一问题,文中提出了一种基于分层率失真优化的容错性转码算法.该算法通过在帧层和宏块层分别对重同步标记的插人和帧内宏块的刷新进行不同粒度的优化来提高算法的灵活性,通过在帧层考虑帧内宏块刷新、帧内预测和运动矢量预测的影响来提高算法的精确性,通过在宏块层减少候选模式的数量来降低算法的复杂度.实验表明,该算法与基于单层率失真优化的算法相比,信噪比可获得0.6～1.1dB的增益,复杂度最多可降低25%.     

一体化承载网络体系架构研究

传统信息网络因面向业务支撑设计而造成体系架构的刚性,无法满足业务发展多样性和网络异构的需求,因此无法适应下一代网络融合、可扩展等特点.面向服务提供的技术体系可以解决这一问题.文中以网络承载服务为核心,以可重构路由交换平台为关键支撑技术,设计出一种面向服务提供的网络体系架构--一体化承载网络(UCN)模型,以及基于UCN模型设计出的逻辑承载网的资源均衡构建算法(RBCA)并进行了网络仿真及结果分析,为下一代网络的研究和设计提供了新的思路.     

A coordinated approach to hedge the risks in stochastic inventory-routing problem

The inventory routing problem (IRP) studied in this research involves repeated delivery of products from a depot to a set of retailers that face stochastic demands over a long period. The main objective in the IRP is to design the set of routes and delivery quantities that minimize transportation cost while controlling inventory costs. Traditional IRP focuses on risk-neutral decision makers, i.e., characterizing replenishment policies that maximize expected total net present value, or equivalently, minimize expected total cost over a planning horizon. In this research, for incorporating risk aversion, a hedge-based stochastic inventory-routing system (HSIRS) integrated with Generalized Autoregressive Conditional Heteroskedasticity (GARCH) model and Forward Option Pricing (FOP)model based on Black-Scholes model, from hedge point of view, is proposed to solve the multi-product multi-period inventory routing problem with stochastic demand. Computational results demonstrate the importance of this approach not only to risk-averse decision makers, but also to maximize the net present value at an acceptable service level. As a result, an optimal portfolio (R, s, S) system of product group can be generated to maximize the net present value under an acceptable service level in a given planning horizon. Meanwhile, the target group needed to be served and the relative transportation policy also can be determined accordingly based on the time required to be served as a priori partition to minimize the average transportation costs; hence, the routing assignment problem can be successfully optimized through a Predicting Particle Swarm Optimization algorithm.     

一种基于ECB模式的NSL协议改进方案

安全协议形式化方法大都在一个很高的抽象层次建立协议模型。但是协议的许多安全问题是在很低的抽象层次产生。本文分析了ECB工作模式下的NSL协议的安全问题,并通过破坏同态性的方法给出一种改进方案。通过扩展规则的BAN逻辑对NSL协议建模和分析,验证结果表明协议中存在着安全漏洞,新的改进方案可以避免这种攻击。     

Deadline division-based heuristic for cost optimization in workflow scheduling

Cost optimization for workflow applications described by Directed Acyclic Graph (DAG) with deadline constraints is a fundamental and intractable problem on Grids. In this paper, an effective and efficient heuristic called DET (Deadline Early Tree) is proposed. An early feasible schedule for a workflow application is defined as an Early Tree. According to the Early Tree, all tasks are grouped and the Critical Path is given. For critical activities, the optimal cost solution under the deadline constraint can be obtained by a dynamic programming strategy, and the whole deadline is segmented into time windows according to the slack time float. For non-critical activities, an iterative procedure is proposed to maximize time windows while maintaining the precedence constraints among activities. In terms of the time window allocations, a local optimization method is developed to minimize execution costs. The two local cost optimization methods can lead to a global near-optimal solution. Experimental results show that DET outperforms two other recent leveling algorithms. Moreover, the deadline division strategy adopted by DET can be applied to all feasible deadlines.     

Adaptive channel and power allocation of downlink multi-user MC-CDMA systems

The Multi-Carrier Code Division Multiple Access (MC-CDMA) is becoming a very attractive multiple access technique for high-rate data transmission in the future wireless communication systems. This paper is focused on the joint channel and power allocation in the downlink transmission of multi-user MC-CDMA systems and considers the throughput maximization problem as a mixed integer optimization problem. For simple analysis, the problem is divided into two less complex sub-problems: power allocation and channel allocation, which can be solved by a suboptimal Adaptive Power Allocation (APA) algorithm and an optimal Adaptive Channel Allocation (ACA) algorithm, respectively. By combining APA and ACA algorithms, an adaptive channel and power allocation scheme is proposed. The numerical results show that the proposed APA algorithm is more suitable for MC-CDMA systems than the conventional equal power allocation algorithm, and the proposed channel and power allocation scheme can significantly improve the system throughput performance.