Transaction Processing in a Mobile,Multi-Database Environment

Current distributed and multi-database systems are designed to allow timely and reliable access to large amounts of data distributed at different locations. Changes in current technology now allow users to access this data via a wide variety of devices through a diverse communication medium. A mobile data access system is an environment in which a wireless-mobile computing environment is superimposed upon a multi-database environment in order to realize anywhere, anytime access capability. As a potentially large number of users may siultaneously access the available data, there are several issues involved in the ability to concurrently manage transactions. Current multi-database concurrency control schemes do not efficiently manage these accesses because they do not address the limited bandwidth and frequent disconnections associated with wirelessnetworks.This paper first introduces the so-called mobile data access system (MDAS) and then proposes a new hierarchical concurrency control algorithm. The proposed concurrency control algorithm, v-lock, uses global locking tables created with semantic information contained within the hierarchy. The locking tables are subsequently used to serialize global transactions, and detect and remove global deadlocks. The performance of the new algorithm is simulated and the results are presented. In addition (through simulation) the performance of the proposed algorithm has been compared and contrasted against the site graph method, the potential conflict graph method, and the forced conflict method     

策略网管中规则冲突检测算法的研究

基于策略的网络管理系统中规则冲突检测是策略管理中的关键部分。多维范围查找算法提供了一种解决检测冲突的思路。设计其中几个子问题的实现技术是重点。进行动作序列有效性检测时,采用了图论知识,详细描述了检测过程并给出了代码实现。进行策略库一致性检测时,将策略规则分解成一些简单数据类型,结合实例加以说明,给出了相关类定义的框架。最后,分析了其时间和空间复杂度,并指出了规则冲突检测中一些可能的工作。     

A Distributed Scheduling Algorithm for Real-Time Communication on Slotted Shared Medium

Algorithms for arbitrating and scheduling transmissions from different transmitters sharing a common access medium arise often in the design of many shared and distributed systems. In this paper we present a distributed algorithm for arbitrating time-constrained transmissions on slotted shared access media. The two most important distinguishing features of our algorithm are: (1) unlike most of the other schemes that guarantee on-time transmission over shared media by centralized preallocation of slots, our algorithm is fully distributed and completely on-line; (2) it eliminates one of the common pitfalls of all slotted systems, that is, allocation in integral multiples of full slots. We derive sufficient conditions for schedulability and show that the proposed scheme achieves high levels of schedulable utilization. We also show that the schedulable utilization increases as the length of the allocation cycle increases and asymptotically approaches the maximum achievable utilization. We present a distributed slot access protocol to realize the proposed algorithm for ring architecture. The protocol can be easily modified for other topologies, such as bus and dual-bus networks. Using illustrative examples we demonstrate the effectiveness of the algorithm.     

基于改进D-S证据理论的室内环境控制决策系统

针对室内环境因子多且相互作用关系复杂,影响室内环境舒适度的控制精准决策,设计了一种基于改进D-S证据理论的室内环境控制决策系统。首先采用箱线图法和均值替代法检测修复异常采集数据,然后利用距离自适应加权融合算法实现同类传感器数据一级融合,最后利用改进D-S证据理论算法,实现全局融合决策。实验结果表明,改进D-S证据理论算法能够有效避免冲突证据带来的融合决策误差,系统可以实现室内环境控制的精准决策,融合决策精度高,具有一定的推广应用价值。     

Optimal routing algorithm and the diameter of the cube-connectedcycles

Communication between processors is one of the most important issues in parallel and distributed systems. The authors study the communication aspects of a well known multiprocessor structure, the cube-connected cycles (CCC). Only nonoptimal routing algorithms and bounds on the diameter of restricted subclasses of the CCC have been presented in earlier work. The authors present an optimal routing algorithm for the general CCC, with a formal proof of its optimality. Based on this routing algorithm, they derive the exact network diameter for the general CCC     

基于改进Dijkstra算法的防冲突最短路径规划研究

多无人机在执行作业任务时可能面临发生航迹冲突的矛盾,由此提出一种改进Dijkstra算法用来实现多无人机寻找最短且互不冲突航线的功能。在经典Dijkstra算法搜寻并对各航迹节点遍历运算的过程中,通过引入各节点的前驱节点变长回溯数组来记录各节点包含的所有前驱节点,找出各任务从起始点到达目标点所存在的全部可行的最短长度航线。再引入时间窗冲突判断模型从各任务的所有可行航线中将互不冲突的航线分离出来,一旦所有航线都冲突,则将其中一条最短航线中的冲突节点当作临时障碍点处理,通过改变回溯数组重新找出与其他任务互不冲突的一条最短航线。应用Matlab软件设计编写程序来进行算法验证,实验表明该改进算法在多无人机执行作业任务时可以规划出各任务包含的全部长度最短且互不冲突的航线,任务集合的规划效率有了明显提高。     

基于超宽带无线传感网络的导频优化脉冲同步算法

超宽带(UWB)技术因具有低功耗、极高时间和空间分辨率等特点成为无线传感网络主要物理层技术之一.本文主要研究基于发送-参考超宽带(TR-UWB)方式的传感网络信号检测与同步技术,文中提出一种新型自适应脉冲同步算法.该算法实现复杂度低,能够快速实现脉冲帧级同步.同步时间仅需要几个符号周期,同时把基于SQP的约束非线性最优化理论应用于设计脉冲导频符号进一步提高同步性能.此外,文中给出了两种脉冲符号级同步方法,它们在不同Eb/No时展现不同性能,可根据实际环境选择最适合的符号级同步方法.脉冲帧级同步具有自适应性,可根据实际的同步性能要求动态调节帧级同步的递归次数.理论分析和计算机仿真验证了该同步算法的性能.     

一种模型重构冲突消解算法

冲突是研究模型重构中的一个重要问题,多数研究将该问题的重点放在冲突检测上,通过对已知冲突的分析,找出冲突消解的手工实现方式.为实现模型重构的自动过程而寻找自动消解冲突的方法是主要研究内容.根据冲突发生的条件将冲突分为3种类型:同一规则的并行使用产生的冲突、对称冲突、非对称冲突.该方法建立在手工分析这3类重构冲突消解的基础上,将重构规则预设为一个规则矩阵,对图转换系统中出现的重构规则进行扫描.扫描结果对照规则矩阵,判断冲突是同一规则还是不同规则的并行使用所产生;分别对这两种情况下的冲突所操作的对象进行分析,根据已有手工消解方法有针对性地进行消解操作.这一算法可以初步实现并行执行的3类冲突的自动消解.     

Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems

We consider broadcasting in random d-regular graphs by using a simple modification of the random phone call model introduced by Karp et al. (Proceedings of the FOCS ’00, 2000). In the phone call model, in every time step, each node calls a randomly chosen neighbour to establish a communication channel to this node. The communication channels can then be used bi-directionally to transmit messages. We show that, if we allow every node to choose four distinct neighbours instead of one, then the average number of message transmissions per node required to broadcast a message efficiently decreases exponentially. Formally, we present an algorithm that has time complexity \(O(\log n)\) and uses \(O(n\log \log n)\) transmissions per message. In contrast, we show for the standard model that every distributed algorithm in a restricted address-oblivious model that broadcasts a message in time \(O(\log n)\) requires \(\Omega (n \log n{/} \log d)\) message transmissions. Our algorithm efficiently handles limited communication failures, only requires rough estimates of the number of nodes, and is robust against limited changes in the size of the network. Our results have applications in peer-to-peer networks and replicated databases.     

An analysis of cube-connected cycles and circular shuffle networks for parallel computation

This paper is concerned with demonstrating isomorphism between two classes of computer architectures that support parallel computation, viz., the cube-connected cycles (CCC) network and the homogeneous circular shuffle network (HCSN). This is done by developing a suitable and common notation for addressing processing elements and specifying interconnections in the two networks. The implications of such an equivalence are discussed. Properties and algorithms concerning HCSN networks, with respect to routing and fault tolerance, thereby, immediately become applicable to CCC networks. As for HCSN networks, their VLSI layout is now apparent. The networks are shown to be totally symmetric with respect to each processor, and in some cases may be recursively defined in terms of modules. Further, any algorithm that runs on an HCSN network also runs on a CCC network without any modification. It is also shown that a large class of algorithms that run on a CCC network can be implemented, with slight modification, on an HCSN network. In particular, an implementation of the DESCENT algorithm on an HCSN network is proposed.     

基于模型预测控制的无人机时空协同航迹规划

为了求解同时实现空间协同和时间协同的多无人机时空协同问题,提出了基于分布式模型预测控制的多无人机在线协同航迹规划的方法。建立了由MPC（Model Predictive Control,）控制器、空间协同模块和时间协同模块组成的多无人机分布式时空协同航迹规划框架结构。MPC将时空协同问题转化为滚动优化问题,优先级的方法实现了空间协同和时间协同的解耦,同时改进了碰撞冲突消解规则,并设计了时间冲突消解规则,解决了分布式时空协同问题的动作一致性问题。仿真实验表明,该方法可以有效地实现多无人时空协同航迹规划。     

The Sound of Silence: Guessing Games for Saving Energy in a Mobile Environment

This paper explores efficient discrete coding techniques that are motivated by the time–energy trade-off in message transmissions between mobile hosts and mobile support stations. Three algorithms are suggested, two of which use guessing games in which the mobile support station guesses the message to be transmitted by the mobile host and receives an approving signal for a successful guess from the mobile host. The first algorithm is designed to achieve the smallest expected amount of energy while obeying a time bound for message transmissions. The second algorithm achieves the shortest expected transmission time while obeying a bound on the energy. This algorithm uses dynamic programming to construct an optimal tree for the guessing game. Our third algorithm uses a different approach based on the Lempel–Ziv compression algorithm. The time–energy trade-off is controlled by the choice of the length of the codes used to encode strings in the dictionary. The theoretical results obtained are not tied to mobile computing and are of independent interest.     

Autonomous fault-diagnosis and decision-making algorithm for determining faulty nodes in distributed wireless networks

In this paper, we address fault-diagnosis agreement (FDA) problems in distributed wireless networks (DWNs) with arbitrary fallible nodes and healthy access points. We propose a new algorithm to reach an agreement among fault-free members about the faulty ones. The algorithm is designed for fully connected DWN and can also be easily adapted to partially connected networks. Our contribution is to reduce the bit complexity of the Byzantine agreement process by detecting the same list of faulty units in all fault-free members. Therefore, the malicious units can be removed from other consensus processes. Also, each healthy unit detects a local list of malicious units, which results in lower packet transmissions in the network. Our proposed algorithm solves FDA problems in 2t+1 rounds of packet transmissions, and the bit complexity in each wireless node is O(n^t+1).     

A pairwise substitutional fault tolerance technique for thecube-connected cycles architecture

With all of the salient features of hypercubes, the cube-connected cycles (CCC) structure is an attractive parallel computation network suited for very large scale integration (VLSI) implementation because of its layout regularity. Unfortunately, the classical CCC structure tends to suffer from considerable performance degradation in the presence of faults. The authors deal with a fault-tolerant CCC structure obtained by incorporating a spare PE in each cycle and by adding extra links among PE's to realize dimensional substitutes for failed PE's in the immediate lower dimension. A unique feature of this design lies in that a faulty PE and its laterally connected PE are always replaced at the same time by their immediate vertical successor pair, achieving pairwise substitution to elegantly maintain the rigid full CCC structure after faulty PE's arise. The proposed structure improves reliability substantially without incurring large overhead in layout area. This design is compared with earlier fault-tolerant CCC designs in terms of normalized reliability, which takes area overhead into account. An extension to this fault-tolerant structure is also discussed     

一种在立方环网络上加总线的方法

本文提出一种在立方环网络（ＣＣＣ）上加总线的方法，对于小规模的ＣＣＣ网络，这种方法能使其直径降为３；而对于大规模的ＣＣＣ网络，能使其直径降为原来的２／３以下，并且还可以使网络中各结点的度降为≤２。     

基于初等运动的多机器人避碰及死锁预防

该文以一实际应用为背景提出了多移动机器人避碰及死锁预防算法,该算法将机器人的运行环境形式化地描述为初等运动集、冲突图、总任务集及机器人作业集,利用集合论、图论的有关方法及技术实现了多机器人间的避碰与死锁预防。当机器人的运行环境改变时,只需要对相应的集合描述文件进行修改,而不用对程序做任何屐改动。算法的另一个特点是利用避碰算法巧妙地完成了死锁预防。仿真和实际运行证明了该算法高效可靠。     

Region-based rate control and bit allocation for wireless video transmission

In this paper, we propose a joint source-channel region-based rate control algorithm for real-time video transmissions over wireless systems. During the video transmission, the channel throughput available to the video encoder in the wireless systems is inherently variable, due to the retransmission of the error packets using the automatic repeat request (ARQ) error control. The variable data rate of the wireless system is characterized by the packet-level Gilbert two-state Markov Model, the parameters of which are extracted from the statistical properties of the channel information obtained from the wireless channel simulator. The proposed algorithm adopts a fast but effective block-based segmentation method to extract the regions of interest. Unlike traditional bit allocation methods used in the region/content-based rate control, the algorithm exploits the most effective criteria "coding qualities" as quantitative factors to directly control bit allocation among different regions so as to achieve better visual quality in the regions of interest. The computational complexity of the algorithm is low making it suitable for real-time applications. Compared with the MPEG-4 rate control algorithm, our algorithm can effectively enhance the perceptual quality for the regions of interest and significantly reduce the number of frame skipping; thereby, improve the smoothness of the video.     

基于MD5算法的身份鉴别技术的研究与实现

MD5报文摘要算法是一种应用广泛的身份认证算法，该文首先对数据加密技术进行了简要的概述，在剖析MD5算法工作原理的基础上，结合DES加密算法，采用加入时间戳、绑定IP地址的基于MD5文摘算法的一次一密方法，给出一个对访问用户口令加密的安全实现，并成功地应用于某高校“艺术类远程招生与考试管理系统”。     

基于冲突水平的多特征离散化方法

在旋转机械故障诊断领域中,通常需要对连续特征量进行离散化预处理,以便后续诊断分析。为此,该文在分析了ChiMerge离散方法及其两点不足的基础上,提出了一种新的基于冲突水平的多特征离散方法。该方法可以自动实现多特征的离散化操作,并且收敛到预设的冲突水平上。算例分析证明了该方法的有效性。     

基于e-制造模式的动态工艺规划技术研究

e-制造工艺系统要求及时准确地根据资源动态信息进行工艺路线的实时决策。该文将工艺规划过程划分为零件信息输入、特征工艺选择和工艺路线的决策等3个阶段，采用神经网络BP算法解决了特征工艺链模糊匹配问题，将资源动态信息与工艺规则共同作为约束条件，采用GA算法实现基于资源动态信息的工艺路线优化选择，有效地解决了调度中的资源冲突问题。采用Java技术开发了软件原型系统，通过实例分析验证了设计方法的可行性。