Partitioning and mapping nested loops on multiprocessor systems

A method for executing nested loops with constant loop-carried dependencies in parallel on message-passing multiprocessor systems to reduce communication overhead is presented. In the partitioning phase, the nested loop is divided into blocks that reduce the interblock communication, without regard to the machine topology. The execution ordering of the iterations is defined by a given time function based on L. Lamport's (1974) hyperplane method. The iterations are then partitioned into blocks so that the execution ordering is not disturbed, and the amount of interblock communication is minimized. In the mapping phase, the partitioned blocks are mapped onto a fixed-size multiprocessor system in such a manner that the blocks that have to exchange data frequently are allocated to the same processor or neighboring processors. A heuristic mapping algorithm for hypercube machines is proposed     

An efficient reliable broadcasting protocol for wireless mobile ad hoc networks

The mobile ad hoc network (MANET) has recently been recognized as an attractive network architecture for wireless communication. Reliable broadcast is an important operation in MANET (e.g., giving orders, searching routes, and notifying important signals). However, using a naive flooding to achieve reliable broadcasting may be very costly, causing a lot of contention, collision, and congestion, to which we refer as the broadcast storm problem. This paper proposes an efficient reliable broadcasting protocol by taking care of the potential broadcast storm problem that could occur in the medium-access level. Existing protocols are either unreliable, or reliable but based on a too costly approach. Our protocol differs from existing protocols by adopting a low-cost broadcast, which does not guarantee reliability, as a basic operation. The reliability is ensured by additional acknowledgement and handshaking. Simulation results do justify the efficiency of the proposed protocol.     

Scalable continuous object detection and tracking in sensor networks

With the advancement of MEMS technologies, sensor networks have opened up broad application prospects. An important issue in wireless sensor networks is object detection and tracking, which typically involves two basic components, collaborative data processing and object location reporting. The former aims to have sensors collaborating in determining a concise digest of object location information, while the latter aims to transport a concise digest to sink in a timely manner. This issue has been intensively studied in individual objects, such as intruders. However, the characteristic of continuous objects has posed new challenges to this issue. Continuous objects can diffuse, increase in size, or split into multiple continuous objects, such as a noxious gas. In this paper, a scalable, topology-control-based approach for continuous object detection and tracking is proposed. Extensive simulations are conducted, which show a significant improvement over existing solutions.     

A Clock Synchronization Algorithm for Multihop Wireless Ad Hoc Networks

In multihop wireless ad hoc networks, it is important that all mobile hosts are synchronized. Synchronization is necessary for power management and for frequency hopping spread spectrum (FHSS) operations. IEEE 802.11 standards specify a clock synchronization protocol but this protocol suffers from the scalability problem due to its inefficiency contention mechanism. In this paper, we propose an automatic self-time-correcting procedure (ASP) to achieve clock synchronization in a multihop environment. Our ASP has two features. First, a faster host has higher priority to send its timing information out than a slower one. Second, after collecting enough timing information, a slower host can synchronize to the faster one by self-correcting its timer periodically (which makes it becoming a faster host). Simulation results show that our ASP decreases 60% the average maximum clock drift as compared to the IEEE 802.11 and reduces 99% the number of asynchronism in a large-scale multihop wireless ad hoc networks.     

A Distributed Query Protocol in Wireless Sensor Networks

In wireless sensor networks, query execution over a specific geographical region is an essential function for collecting sensed data. However, sensor nodes deployed in sensor networks have limited battery power. Hence, the minimum number of connected sensor nodes that covers the queried region in a sensor network must be determined. This paper proposes an efficient distributed protocol to find a subset of connected sensor nodes to cover the queried region. Each node determines whether to be a sensing node to sense the queried region according to its priority. The proposed protocol can efficiently construct a subset of connected sensing nodes and respond the query request to the sink node. In addition, the proposed protocol is extended to solve the k-coverage request. Simulation results show that our protocol is more efficient and has a lower communication overhead than the existing protocol.     

An optimal broadcasting algorithm without message redundancy instar graphs

Based on the V.E. Mendia and D. Sarkar's algorithm (1992), we propose an optimal and nonredundant distributed broadcasting algorithm in star graphs. For an n-dimensional star graph, our algorithm takes O(n log₂ n) time and guarantees that all nodes in the star graph receive the message exactly once. Moreover, broadcasting m packets in a pipeline fashion takes O(m log₂ n+n log₂ n) time due to the nonredundant property of our broadcasting algorithm     

Selection of the first k largest processes in hypercubes

In this paper, algorithms are proposed for finding the first k largest numbered processes in hypercubes with and without faulty nodes.     

A Distributed Localization Scheme for Wireless Sensor Networks with Improved Grid-Scan and Vector-Based Refinement

Localization is a fundamental and essential issue for wireless sensor networks (WSNs). Existing localization algorithms can be categorized as either range-based or range-free schemes. Range-based schemes are not suitable for WSNs because of their irregularity of radio propagation and their cost of additional devices. In contrast, range-free schemes do not need to use received signal strength to estimate distances and only need simple and cheap hardware, and are thus more suitable for WSNs. However, existing range-free schemes are too costly and not accurate enough or are not scalable. To improve previous work, we present a fully distributed range-free localization scheme for WSNs. We assume that only a few sensor nodes, called anchors, know their locations, and the remaining (normal) nodes need to estimate their own locations by gathering nearby neighboring information. We propose an improved grid-scan algorithm to find the estimated locations of the normal nodes. Furthermore, we derive a vector-based refinement scheme to improve the accuracy of the estimated locations. Analysis, simulation, and experiment results show that our scheme outperforms the other range-free schemes even when the communication radius is irregular.     

A traffic-aware scheduling for bluetooth scatternets

Bluetooth is a low cost, low power, short-range radio technology used for wireless personal area networks (PANS). Bluetooth scatternet is a set of piconets interconnected via bridge devices. Good interpiconet schedulings are necessary for bridge devices to switch among piconets they participate in. This paper proposes an interpiconet scheduling algorithm named "Traffic-Aware Scatternet Scheduling" (TASS), for bridges in Bluetooth scatternets. According to masters' traffic information, TASS can adaptively switch the bridge to high traffic load masters, and increase the usage of the bridge. In addition, TASS can reduce the number of failed "unsniffs" and the overhead of "bridge switch wastes" to further increase overall system performance. Simulation results show that TASS outperforms existing interpiconet scheduling in both network throughput and adaptability for various traffic loads.     

Partitioning and mapping of nested loops for linear array multicomputers

In distributed-memory multicomputers, minimizing interprocessor communication is the key to the efficient execution of parallel programs. In order to reduce the amount of communication overhead, parallel programs on multicomputers must be carefully scheduled by parallelizing compilers. This paper proposes some compilation techniques for partitioning and mapping nested loops with constant data dependences onto linear array multicomputers. First, a systematic partition strategy is proposed to project ann-dimensional computational structure, representing ann-nested loop, onto a line to form a one-dimensional projected structure with low communication overhead. Then, a mapping algorithm is proposed for mapping the partitioned loops onto linear arrays in a way that balances the workload and minimizes the communication cost among processors. Finally, parallel execution codes can be automatically generated for such linear array multicomputers.