A Constant-Competitive Algorithm for Online OVSF Code Assignment

Orthogonal Variable Spreading Factor (OVSF) code assignment is a fundamental problem in Wideband Code-Division Multiple-Access (W-CDMA) systems, which plays an important role in third generation mobile communications. In the OVSF problem, codes must be assigned to incoming call requests with different data rate requirements, in such a way that they are mutually orthogonal with respect to an OVSF code tree. An OVSF code tree is a complete binary tree in which each node represents a code associated with the combined bandwidths of its two children. To be mutually orthogonal, each leaf-to-root path must contain at most one assigned code. In this paper, we focus on the online version of the OVSF code assignment problem and give a 10-competitive algorithm (where the cost is measured by the total number of assignments and reassignments used). Our algorithm improves the previous O(h)-competitive result, where h is the height of the code tree, and also another recent constant-competitive result, where the competitive ratio is only constant under amortized analysis and the constant is not determined. We also improve the lower bound of the problem from 3/2 to 5/3.     

多标签快速识别算法的研究

解决RFID多标签碰撞问题常用的时隙aloha方法效率较低,二进制树方法要求区域内标签数喇不变.以提高aloha法的标签识别效率为目的,分析不同时隙内标签的碰撞个数,构建了标签碰撞的分布数学模型,分析最大时隙利用率,提出了一种多标签快速识别算法.该算法以阅读器发出的Query命令决定的时隙数为一段观察时间,对期间的标签响应状况进行统计分析以便对下一轮识别做出正确的指导,是一种动态帧时隙aloha算法.Msdab仿真结果表明,物流射频识别系统中,算法比时隙aloha算法的识别效率提高近一倍.     

An Algorithmic View on OVSF Code Assignment

Orthogonal Variable Spreading Factor (OVSF) codes are used in UMTS to share the radio spectrum among several connections of possibly different bandwidth requirements. The combinatorial core of the OVSF code assignment problem is to assign some nodes of a complete binary tree of height h (the code tree) to n simultaneous connections, such that no two assigned nodes (codes) are on the same root-to-leaf path. A connection that uses a 2^-d fraction of the total bandwidth requires some code at depth d in the tree, but this code assignment is allowed to change over time. Requests for connections that would exceed the total available bandwidth are rejected. We consider the one-step code assignment problem: Given an assignment, move the minimum number of codes to serve a new request. Minn and Siu propose the so-called DCA algorithm to solve the problem optimally. In contrast, we show that DCA does not always return an optimal solution, and that the problem is NP-hard. We give an exact n^O(h)-time algorithm, and a polynomial-time greedy algorithm that achieves approximation ratio Θ(h). A more practically relevant version is the online code assignment problem, where future requests are not known in advance. Our objective is to minimize the overall number of code reassignments. We present a Θ(h)-competitive online algorithm, and show that no deterministic online algorithm can achieve a competitive ratio better than 1.5. We show that the greedy strategy (minimizing the number of reassignments in every step) is not better than Ω(h) competitive. We give a 2-resource augmented online algorithm that achieves an amortized constant number of (re-)assignments. Finally, we show that the problem is fixed-parameter tractable.     

Distributed Latency-Energy Minimization and interference avoidance in TDMA Wireless Sensor Networks

This paper presents Latency-Energy Minimization Medium Access (LEMMA), a new TDMA-based MAC protocol for Wireless Sensor Networks (WSNs), specially suited to extend the lifetime of networks supporting alarm-driven, delay-sensitive applications characterized by convergecast traffic patterns and sporadic traffic generation. Its cascading time-slot assignment scheme conciliates low end-to-end latency with a low duty-cycle, while supporting multi-sink WSN topologies. Unlike most of the current solutions, LEMMA’s time-slot allocation protocol makes decisions based on the interference actually experienced by the nodes, instead of following the simple but potentially ineffective n-hop approach. Simulation results are presented to demonstrate the ineffectiveness of the n-hop time-slot allocation in comparison with LEMMA, as well as to evaluate the performance of LEMMA against L-MAC, T-MAC and Low Power Listening. The results show that under the target scenario conditions, LEMMA presents lower interference between assigned time-slots and lower end-to-end latency, while matching its best contender in terms of energy-efficiency.     

OVSF-CDMA Code Assignment in Wireless Ad Hoc Networks

Orthogonal Variable Spreading Factor (OVSF) CDMA code consists of an infinite number of codewords with variable rates, in contrast to the conventional orthogonal fixed-spreading-factor CDMA code. Thus, it provides a means of supporting of variable rate data service at low hardware cost. However, assigning OVSF-CDMA codes to wireless ad hoc nodes posts a new challenge since not every pair of OVSF-CDMA codewords are orthogonal to each other. In an OVSF-CDMA wireless ad hoc network, a code assignment has to be conflict-free, i.e., two nodes can be assigned the same codeword or two non-orthogonal codewords if and only if their transmission will not interfere with each other. The throughput (resp., bottleneck) of a code assignment is the sum (resp., minimum) of the rates of the assigned codewords. The max-throughput (resp., max-bottleneck) conflict-free code assignment problem seeks a conflict-free code assignment which achieves the maximum throughput (resp., bottleneck). In this paper, we present several efficient methods for conflict-free code assignment in OVSF-CDMA wireless ad hoc networks. Each method is proved to be either a constant-approximation for max-throughput conflict-free code assignment problem, or a constant-approximation for max-bottleneck conflict-free code assignment problem, or constant-approximations for both problems simultaneously. The work of Peng-Jun Wan and Xiang-Yang Li is partially supported by NSF CCR-0311174. The preliminary version of the paper first appeared in ACM DIAL M-POMC 2004, workshop of ACM MobiCom 2004.     

Distributed scheduling algorithms for channel access in TDMA wireless mesh networks

In this paper, we have considered the distributed scheduling problem for channel access in TDMA wireless mesh networks. The problem is to assign time-slot(s) for nodes to access the channels, and it is guaranteed that nodes can communicate with all their one-hop neighbors in the assigned time-slot(s). And, the objective is to minimize the cycle length, i.e., the total number of different time-slots in one scheduling cycle. In single-channel ad hoc networks, the best known result for this problem is proved to be K ² in arbitrary graphs (Chlamtac and Pinter in IEEE Trans. Comput. C-36(6):729–737, 1987) and 25K in unit disk graphs () with K as the maximum node degree. There are multiple channels in wireless mesh networks, and different nodes can use different control channels to reduce congestion on the control channels. In this paper, we have considered two scheduling models for wireless mesh networks. The first model is that each node has two radios, and the scheduling is simultaneously done on the two radios. We have proved that the upper bound of the cycle length in arbitrary graphs can be 2K. The second model is that the time-slots are scheduled for the nodes regardless of the number of radios on them. In this case, we have proved that the upper bound can be (4K−2). We also have proposed greedy algorithms with different criterion. The basic idea of these algorithms is to organize the conflicting nodes by special criterion, such as node identification, node degree, the number of conflicting neighbors, etc. And, a node cannot be assigned to a time-slot(s) until all neighbor nodes, which have higher criterion and might conflict with the current node, are assigned time-slot(s) already. All these algorithms are fully distributed and easy to realize. Simulations are also done to verify the performance of these algorithms.     

Distributed scheduling algorithms for channel access in TDMA wireless mesh networks

In this paper, we have considered the distributed scheduling problem for channel access in TDMA wireless mesh networks. The problem is to assign time-slot(s) for nodes to access the channels, and it is guaranteed that nodes can communicate with all their one-hop neighbors in the assigned time-slot(s). And the objective is to minimize the cycle length, i.e., the total number of different time-slots in one scheduling cycle. In single-channel ad hoc networks, the best known result for this problem is proved to be K ² in arbitrary graphs (IEEE Trans Comput C-36(6):729–737, 1987) and 25K in unit disk graphs (IEEE/ACM Trans Netw pp 166–177, 1993) with K as the maximum node degree. There are multiple channels in wireless mesh networks, and different nodes can use different control channels to reduce congestion on the control channels. In this paper, we have considered two scheduling models for wireless mesh networks. The first model is that each node has two radios, and the scheduling is simultaneously done on the two radios. We have proved that the upper bound of the cycle length in arbitrary graphs can be 2K. The second model is that the time-slots are scheduled for the nodes regardless of the number of radios on them. In this case, we have proved that the upper bound can be (4K?2). We also have proposed greedy algorithms with different criterion. The basic idea of these algorithms is to organize the conflicting nodes by special criterion, such as node identification, node degree, the number of conflicting neighbors, etc. And a node cannot be assigned to a time-slot(s) until all neighbor nodes, which have higher criterion and might conflict with the current node, are assigned time-slot(s) already. All these algorithms are fully distributed and easy to realize. Simulations are also done to verify the performance of these algorithms.     

一种支持OVSF码重分配的下行带宽分配算法

WCDMA的下行链路中,OVSF码被用作区分不同物理信道的信道化码,以最大程度降低UE的多址接入干扰(MAI),并提供对可变速率的支持。所以OVSF码的分配策略及算法直接影响网络的整体性能。该文分析了DCA算法的不足之处并提出了一种支持重分配的多码分配算法。仿真结果表明,该算法能在保持下行链路带宽利用率的同时,有效地减少OVSF码树的碎片并减轻重分配给系统带来的影响。     

A gradual neural-network approach for frequency assignment insatellite communication systems

A novel neural-network approach called gradual neural network (GNN) is presented for a class of combinatorial optimization problems of requiring the constraint satisfaction and the goal function optimization simultaneously. The frequency assignment problem in the satellite communication system is efficiently solved by GNN as the typical problem of this class. The goal of this NP-complete problem is to minimize the cochannel interference between satellite communication systems by rearranging the frequency assignment so that they can accommodate the increasing demands. The GNN consists of NxM binary neurons for the N-carrier-M-segment system with the gradual expansion scheme of activated neurons. The binary neural network achieves the constrain satisfaction with the help of heuristic methods, whereas the gradual expansion scheme seeks the cost optimization. The capability of GNN is demonstrated through solving 15 instances in practical size systems, where GNN can find far better solutions than the existing algorithm.     

Energy Efficient Monitoring in Sensor Networks

We study a set of problems related to efficient battery energy utilization for monitoring applications in a wireless sensor network with the goal to increase the sensor network lifetime. We study several generalizations of a basic problem called Set k-Cover. The problem can be described as follows: we are given a set of sensors, and a set of targets to be monitored. Each target can be monitored by a subset of the sensors. To increase the lifetime of the sensor network, we would like to partition the sensors into k sets (or time-slots), and activate each set of sensors in a different time-slot, thus extending the battery life of the sensors by a factor of k. The goal is to find a partitioning that maximizes the total coverage of the targets for a given k. This problem is known to be NP-hard. We develop an improved approximation algorithm for this problem using a reduction to Max k-Cut. Moreover, we are able to demonstrate that this algorithm is efficient, and yields almost optimal solutions in practice.     

基于两次应用优先级的GDP时隙分配算法模型

地面等待策略是空中交通流量管理中主要采用的一种方法,文中主要介绍了基于两次应用优先级的GDP时隙分配算法。初次优先级的使用是达到分组的目的,再次应用优先级则是为了解决初次分配后可能存在的在同一分组中航班竞争同一时隙的问题。文中对相应的算法实现做了详细介绍,并对成都双流机场的航班进行了多次仿真实验。同时和单纯的基于优先级的方法进行了对比,验证了该算法的可行性。     

Routing wavelength and time-slot reassignment algorithms for TDM based optical WDM networks

In this paper, we consider the problem of maximizing the time of first lightpath request rejection, T in the circuit-switched time division multiplexed (TDM) wavelength-routed (WR) optical WDM networks. TDM is incorporated into WDM, to increase the channel utilization when the carried traffic does not require the entire channel bandwidth. In TDM–WDM network, multiple sessions are multiplexed on each wavelength by assigning a sub-set of the TDM slots to each session. Thus, given a session request with a specified bandwidth, a lightpath has to be established by using the routing, wavelength and time-slot assignment (RWTA) algorithms. If the lightpath cannot be established, lightpath request rejection or call blocking occurs. As each lightpath is substantial revenue and long-lived, lightpath request rejection is highly unfavourable in the optical backbone networks. In this paper, we are proposing an intelligent routing, wavelength and time-slot reassignment algorithm for multi-rate traffic demands, where, when a call gets blocked, the already established calls in the network are rerouted, wavelength and time-slot reassigned so as to accommodate the blocked call. Since we are talking of slow arrivals and long holding times for the lightpaths, it is possible to do this reassignment while provisioning a new call. Simulation based analyses are used to study the performance of the proposed reassignment algorithm. The results show that the proposed reassignment algorithm can be used to maximize the time of first call blocking, thereby accommodating more calls in the network before upgrading the network capacity.     

Links organization for channel assignment in multi-radio wireless mesh networks

It is one key issue in the wireless mesh networks to provide various scenarios such as multimedia and applications. Links in the network can be organized and assigned to orthogonal channels so as to minimize the co-channel interference. In this paper we focus on the channel assignment problem for links in the mesh networks and aim at minimizing the overall network interference. The problem is proved to be NP-hard. We have first formulated an approach based on the Particle Swarm Optimization (PSO) algorithm which can be used to find the approximate optimized solution in small-size networks and as a baseline that other algorithms can be compared with. We also have proposed a centralized heuristic as well as a distributed heuristic algorithm for the channel assignment problem. Extensive simulation results have demonstrated that our schemes have good performance in both dense and sparse networks compared with related works.     

无线传感器网中基于时隙轮循的串音控制策略

提出了一种基于时隙轮循的无线传感器网络MAC协议串音控制策略。此策略以簇结构组织网络,由簇头为簇内节点分配互不重叠的工作时隙,并以自带信令的方式来避免节点之间可能的串音。理论分析及仿真表明采用时隙轮循的串音控制策略有效地减少了节点间的串音,提高了无线传感器网络MAC协议的能量有效性。     

On Walsh code assignment

We consider the problem of orthogonal variable spreading Walsh code assignments. The aim is to provide assignments that can avoid both complicated signaling from the BS to the users and blind rate and code detection amongst a great number of possible codes. The assignments considered here use partitioning of all users into several pools. Each pool can use its own codes, which are different for different pools. Each user has only a few codes assigned to it within the pool. We state the problem as a combinatorial one expressed in terms of a binary n × k matrix M where n is the number of users and k is the number of Walsh codes in the pool. A solution to the problem is given as a construction of a matrix M which has the assignment property defined in the paper. Two constructions of such M are presented under different conditions on n and k. The first construction is optimal in the sense that it gives the minimal number of Walsh codes — assigned to each user for given n and k. The optimality follows from a proved necessary condition for the existence ofM with the assignment property. In addition, we propose a simple algorithm of optimal assignment for the first construction.     

基于概率的水下传感器网络CDMA编码分配算法

水下传感器网络采用声波进行通信,具有高时延、低带宽、高误码率等特点,使得适用于无线电信道的MAC协议无法直接应用于水声信道,给水下传感器网络协议的设计带来了很大的挑战．因此,我们提出了一种可以较高概率避免扩频码冲突的分布式的基于概率的水下传感器网络CDMA编码动态分配算法．该算法不需要精确的时间同步,并且能够动态适应水下传感器网络拓扑结构的变化,适用于基于发送端的编码分配和基于接收端的编码分配．仿真实验表明,与传统的编码分配方式相比,我们的算法突出了节点的个性化,进一步降低了冲突的风险．     

基于TDMA的星间链路时隙分配设计与仿真评估

基于TDMA的星间链路体制组网灵活,传输效率高,已成为今后星间链路的一种发展趋势;对于TDMA的星座网络而言,其时隙分配是影响业务时延的重要因素,文章就一种双层混合型星座提出了一种时隙分配方案,并对星座网络的传输进行了仿真,分别从广播和单播两种业务的角度针对星间链路传输性能的时延指标进行了评估分析,结果显示,该TDMA星座网络基本能在30s内广播全网数据,且单播时在地面站仰角不受限的情况下,绝大部分(95%以上)的境外星最多都只需要一跳即可到达,该结果会在地面站仰角限制增大的情况下随之递减。     

Multi-start stochastic competitive Hopfield neural network for frequency assignment problem in satellite communications

The objective of the frequency assignment problem (FAP) is to minimize cochannel interference between two satellite systems by rearranging frequency assignment. In this paper, we first propose a competitive Hopfield neural network (CHNN) for FAP. Then we propose a stochastic CHNN (SCHNN) for the problem by introducing stochastic dynamics into the CHNN to help the network escape from local minima. In order to further improve the performance of the SCHNN, a multi-start strategy or re-start mechanism is introduced into the SCHNN. The multi-start strategy or re-start mechanism super-imposed on the SCHNN is characterized by alternating phases of cooling and reheating the stochastic dynamics, thus provides a means to achieve an effective dynamic or oscillating balance between intensification and diversification during the search. Furthermore, dynamic weighting coefficient setting strategy is adopted in the energy function to satisfy the constraints and improve the objective of the problem simultaneously. The proposed multi-start SCHNN (MS-SCHNN) is tested on a set of benchmark problems and a large number of randomly generated instances. Simulation results show that the MS-SCHNN is better than several typical neural network algorithms such as GNN, TCNN, NCNN and NCNN-VT, and metaheuristic algorithm such as hybrid SA.     

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

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

An efficient cluster-based CDMA/TDMA scheme for wireless mobile ad-hoc networks: A learning automata approach

In this paper, we design a dynamic frame length CDMA/TDMA scheme for clustered wireless ad hoc networks with unknown traffic parameters. In this scheme, the collision-free intra-cluster communications are organized by the cluster-heads using a TDMA scheme, and a CDMA scheme is overlaid on the TDMA to organize the interference-free inter-cluster communications. Therefore, to design such a scheme, we encounter three important problems, namely cluster formation, code assignment, and slot assignment. In this paper, we propose three algorithms to solve the addressed problems based on learning automata. In our scheme, by the proposed clustering algorithm, the wireless hosts are grouped into non-overlapping clusters. Then, by the proposed code assignment algorithm (considering the concept of code spatial reuse), an interference-free code is assigned to each cluster. Finally, by the slot assignment algorithm, each cluster member is assigned a fraction of TDMA frame proportional to its traffic load. The simulation results show that the proposed CDMA/TDMA scheme outperforms the existing methods in terms of almost all metrics of interest, specifically, under bursty traffic conditions.