Optimal task assignment in homogeneous networks

This paper considers the problem of assigning the tasks of a distributed application to the processors of a distributed system such that the sum of execution and communication costs is minimized. Previous work has shown this problem to be tractable for a system of two processors or a linear array of N processors, and for distributed programs of serial parallel structures. Here we focus on the assignment problem on a homogeneous network, which is composed of N functionally-identical processors, each with its own memory. Some processors in the network may have unique resources, such as data files or certain peripheral devices. Certain tasks may have to use these unique resources; they are called attached tasks. The tasks of a distributed program should therefore be assigned so as to make use of specific resources located at certain processors in the network while minimizing the amount of interprocessor communication. The assignment problem in such a homogeneous network is known to be NP-hard even for N=3, thus making it intractable for a network with a medium to large number of processors. We therefore focus on task assignment in general array networks, such as linear arrays, meshes, hypercubes, and trees. We first develop a modeling technique that transforms the assignment problem in an array or tree into a minimum-cut maximum-flow problem. The assignment problem is then solved for a general array or tree network in polynomial time     

Optimal replication algorithms for hierarchical mobility management in PCS networks

In the context of heterogeneous networks and diverse communication devices, real person-to-person communication can be achieved with a universal personal identification (UPI) that uniquely identifies an individual and is independent of the access networks and communication devices. Hierarchical mobility management techniques (MMTs) have been proposed to support UPI. Traditional replication methods for improving the performance of such MMTs are threshold based. In this paper, we present optimal replication algorithms that minimize the network messaging cost based on network structure, communication link cost, and user calling and mobility statistics. We develop our algorithms for both unicast and multicast replica update strategies. The performance of these replication algorithms is studied via large scale network simulations and compared to results obtained from the threshold-based method.     

A location-based mobility tracking scheme for PCS networks

This paper introduces a location-based locating strategy for Personal Communication Services (PCS) systems. In the proposed scheme, location updates are based on the value of a movement counter. The update of the movement counter is based on information on the locations visited by a mobile terminal (MT) since the last location update. In particular, the cell identifiers and the corresponding movement counter values are maintained in the MT for a part of the visited cells since the last location update. When the MT enters a cell whose identifier is not stored in the MT, the movement counter increases by one. If the movement counter reaches the update threshold, a location update is triggered; otherwise, the cell identifier and the corresponding movement counter value are stored in the MT. When the MT enters a cell whose identifier is in the MT, the movement counter is assigned with the counter value kept in the MT for this cell, and all cells with greater counter values in the MT are removed. The proposed scheme allows the dynamic selection of the update threshold according to each user's calling and mobility patterns. Analytical and simulation models have been developed to compare the proposed scheme with both the movement-based scheme and the distance-based scheme. Results demonstrate that when the call-to-mobility ratio (CMR) is low, the proposed scheme can achieve a significant cost reduction compared to the movement-based scheme. For example, when the CMR is 0.01, a savings of around 25% in the optimal total cost per call arrival is achieved with the proposed scheme. Moreover, the proposed scheme is easier to implement than the distance-based scheme.     

PCS网络位置管理方案性能分析

PCS（Personal Communication Service）网络中位置管理开销昂贵；为减小开销，研究人员提出了许多种方案。研究了基于LRA（Lazy Replication Algorithm）的位置管理方案，建立了分析模型，以相邻两次呼叫期间实现位置管理所花费的开销为指标，对IS-41和LRA两者的性能进行了比较。研究表明，对于高移动性或远离归属地的用户，LRA显著优于IS-41；另一方面，对于呼叫多发生于两个服务区间或低移动性的用户，IS-41优于LRA；从总体上看，LRA性能优于IS-41。     

Distributed cell-centric neighborhood-related location area planning for PCS networks

An intelligent location area planning (LAP) scheme should consider the frequent replannings of location areas (LAs) due to changes in user distribution and mobility patterns along with optimization of location management costs, including location updating and paging costs. Most schemes proposed in the literature are designed through centralized techniques, thus requiring more computing time to plan the LAs. Frequent replannings to accommodate environmental changes make the situation worse. As to the optimization of location management costs, most proposed schemes consider the inter-cell crossing rate as one of the key factors in determining the optimal partitions. In some cases, the inter-cell crossing rate may lead to an unsatisfactory outcome. Another problem is the ping-pong effect which is caused by the fixed borders between any two of LAs. In this paper, we propose a distributed cell-centric neighborhood-related LAP scheme in which each cell acts as the center of an LA and in which highly correlative neighboring cells are bundled into the LA if mobile terminals (MTs) remain within the LA long enough to reduce costs. Moreover, the ping-pong effect will be alleviated because MTs always locate at the center cell of an LA whenever a new location update is performed. Finally, the scheme can be implemented in a distributed manner so the computing time incurred by frequent replannings can be reduced. Simulation results show that our scheme indeed exhibits excellent results.     

异构网络中贪婪资源分配策略的研究

针对当前异构网络中多种业务并存的现状,提出了一种可应用于由移动微波存取全球互通和通用移动通信系统组成的异构网络中考虑切换业务优先的贪婪资源分配策略,并通过网络中的呼损率验证了该策略的可行性;接着,在NS2环境下将该策略与公平资源分配策略在资源利用率、分组丢失率方面进行了比较.仿真结果显示,新策略可以提供良好的服务质量,前者的资源利用率和分组丢失率比后者分别改善了13％和14％左右.     

Optimal constant due-date assignment and sequencing

This paper considers the sequencing of n jobs in a single-machine shop in which each job is assigned a constant flow allowance. The objective is to determine the optimal value of the flow allowance and the optimal job sequence to minimize a cost function based on the flow allowance and the job earliness and tardiness values. We first propose a linear programming (LP) formulation of the problem. We then derive the optimal constant flow allowance via considering the LP dual problem and show that it is independent of the job sequence. After the theoretical treatment, a numerical example is presented for discussion.     

Primal and dual assignment networks.

This paper presents two recurrent neural networks for solving the assignment problem. Simplifying the architecture of a recurrent neural network based on the primal assignment problem, the first recurrent neural network, called the primal assignment network, has less complex connectivity than its predecessor. The second recurrent neural network, called the dual assignment network, based on the dual assignment problem, is even simpler in architecture than the primal assignment network. The primal and dual assignment networks are guaranteed to make optimal assignment. The applications of the primal and dual assignment networks for sorting and shortest-path routing are discussed. The performance and operating characteristics of the dual assignment network are demonstrated by means of illustrative examples.     

Location management based on distance and direction for PCS networks

This paper proposes a distance-and-direction-based location management scheme with a nonisotropic mobility model to capture the directional movement of an MT, which remarkably reduces the total cost at the cost of a slight increase in the location update cost. In this scheme, whenever a distance threshold or a direction threshold is exceeded, a location update is performed. When a call arrives, the network pages the called MT within the paging area defined by the distance threshold and direction threshold. In addition, an online distance-and-direction calculation method, and an interactive distance-and-direction optimization algorithm are developed to dynamically adjust the paging area. We analyze this scheme using a Markov chain for both one-dimensional (1-D) case and two-dimensional (2-D) case. Specifically, a good state coalition method is proposed to reduce sharply the computational complexity of the 2-D cost evaluation. Numerical results suggest that substantial cost saving can be obtained by fully utilizing the mobility direction information. Therefore, the proposed scheme outperforms the distance-based scheme.     

Optimal due date assignment in multi-machine scheduling environments

We study two due date assignment problems in various multi-machine scheduling environments. We assume that each job can be assigned an arbitrary non-negative due date, but longer due dates have higher cost. The first problem is to minimize a cost function, which includes earliness, tardiness and due date assignment costs. In the second problem, we minimize an objective function which includes the number of tardy jobs and due date assignment costs. We settle the complexity of many of these problems by either showing that they are -hard or by providing a polynomial time solution for them. We also include approximation and non-approximability results for several parallel-machine problems. This research was partially supported by the Paul Ivanier Center for Robotics and Production Management, Ben-Gurion University of the Negev. Partial support by the Natural Sciences and Engineering Research Council of Canada under Grant No. 041798 is also gratefully acknowledged.     

Analysis and design of primal-dual assignment networks

The assignment problem is an archetypical combinatorial optimization problem having widespread applications. This paper presents two recurrent neural networks, a continuous-time one and a discrete-time one, for solving the assignment problem. Because the proposed recurrent neural networks solve the primal and dual assignment problems simultaneously, they are called primal-dual assignment networks. The primal-dual assignment networks are guaranteed to make optimal assignment regardless of initial conditions. Unlike the primal or dual assignment network, there is no time-varying design parameter in the primal-dual assignment networks. Therefore, they are more suitable for hardware implementation. The performance and operating characteristics of the primal-dual assignment networks are demonstrated by means of illustrative examples.     

多信道无线Mesh网络信道分配算法

针对无线Mesh网络的带宽容量问题,文章通过使用无线网络干扰协议模型对无线链路的干扰进行量化,利用整数线性规划公式对信道分配问题进行描述,在信道分配的时候,应用目标函数对无线链路的信道分配进行优化,使网络总的干扰权重最小化,在此基础上提出一个信道分配的启发式算法。仿真结果表明,文章提出的算法能提高网络的吞吐量。     

多射频无线网络中多信道分配方法的研究

针对多射频多信道无线网络信道分配中用户收益不均衡和网络资源利用率低的问题,给出了一种基于博弈论的信道分配策略,该策略在考虑信道分配有效性、公平性的同时,基于不完美信息博弈,给出了一种使网络负载更均衡的算法,并通过实验仿真验证了算法的鲁棒性和有效性。     

Optimal polling in communication networks

Polling is the process in which an issuing node of a communication network (polling station) broadcasts a query to every other node in the network and waits to receive a unique response from each of them. Polling can be thought of as a combination of broadcasting and gathering and finds wide applications in the control of distributed systems. In this paper, we consider the problem of polling in minimum time. We give a general lower bound on the minimum number of time units to accomplish polling in any network and we present optimal polling algorithms for several classes of graphs, including hypercubes and recursively decomposable Cayley graphs     

Adaptive channel assignment scheme for wireless networks

In this paper, an adaptive channel assignment scheme is proposed to ensure the quality of services for the wireless networks. The proposed scheme divides the channels into two categories, the guard channels and the shared channels. The number of guard channels is estimated by the Markovian model in order to keep the handoff calls higher priority. The remaining channels, called shared channels, can be used by both new calls and handoff calls. The proposed scheme based on incoming rates of handoff and new calls allocates channels for guard and shared channels. In addition, this approach is able to provide quality of service guarantee in terms of handoff dropping rate. From the simulation, the proposed scheme significantly improves the dropping rate and the blocking rate in comparison with the existing methods.     

Competition Based Neural Networks for Assignment Problems

Competition based neural networks have been used to solve the generalized assignment problem and the quadratic assignment problem.Both problems are very difficult and are ε approximation complete.The neural network approach has yielded highly competitive performance and good performance for the quadratic assignment problem.These neural networks are guaranteed to produce feasible solutions.