The Recursively Decomposable Interconnection Network (RDIN) is a set of interconnection networks that can be recursively decomposed into smaller substructures whose topologies and properties are similar to the original one. The examples of the RDIN are hypercubes, star graph, mesh, tree, pyramid, pancake, and WK-recursive network. This paper proposed a uniform and simple model to represent the RDIN inside computers at first. Based on the model, a generalized and efficient allocation scheme capable of being applied to all the members of the RDIN is developed. The proposed scheme can fully recognize the substructures (such as subcube, substar, subtree,. . . ) more easily than ever, and it is the first one that can fully recognize all the incomplete substructures. The best-fit allocation is also proposed. The criterion aims at keeping the largest free parts from being destroyed, as is the philosophy of the best-fit allocation. Moreover, the proposed scheme can be performed in an injured RDIN with its processors and/or links faulty. Finally, the mathematical analysis and simulations for two instances, hypercubes and star graphs, of the RDIN are presented. The results show that the generalized scheme outperforms or is comparable to the other proprietary allocation schemes designed for the specific structure.

The star graph has been known as an attractive alternative to the hypercube multiprocessor. Like the hypercube, the star graph possesses the properties of symmetry, partionability and fault tolerance, but with a smaller diameter and degree than those of the hypercube. When tasks arrive at the star graph, the tasks should be assigned appropriate free processors before execution. A new model, called Star graph (Sg)-lattice, is proposed to model the construction and free configuration of the star graph. Based on this model, the Sg-lattice scheme can fully recognize the substars. Finally, mathematical analyses and simulation results show that the Sg-lattice scheme outperforms the previous work in the storage and time complexities and the average allocation time.

An ad hoc network is formed by a group of mobile hosts communicating over wireless channels. There is no any fixed network interaction and centralized administration. Because a routing protocol needs an efficient medium access control (MAC) protocol to support, to design an efficient MAC protocol is important and fundamental in ad hoc networks. So far, no other MAC protocol has stable broadcast performance in the dense mobile ad hoc network. In this paper, we address the issue of reliable broadcast and stable performance at the MAC layer. We present a reliable and adaptive broadcast MAC protocol RAMAC which is a TDMA-based distributed MAC protocol for the broadcast reservation in mobile ad hoc networks. We divide the area into many grid cells with the support of GPS. We use the properties of grid cells to design an efficient protocol. RAMAC is characterized by five important features: (i) A dynamic frame size is generated in every contention. This dynamic frame size can let RAMAC adapt to the network load. (ii) Our well-designed reservation protocol can avoid the deadlock problem. (iii) When the network is dense, RAMAC can still work stably; however, no other MAC protocols can work well in the dense network. (iv) We propose a reservation protocol that can efficiently and fast reserve data slots. (v) The well-designed grid architecture makes the senders of unicast in a grid cell transmit concurrently as many as possible, so RAMAC is highly parallel in unicast.