Annual Review 2010 > Division of Computer Engineering

Performance Evaluation Laboratory

Kouhei Otsuyama

Assistant Professor

Song Guo

Assistant Professor

Shui Yu

Visiting Researcher

The laboratory mission in the broad sense is to contribute to:

Energy-efficient Computing in Distributed Wireless Sensor Networks

Recently, research on wireless sensor networks (WSNs) has intensified, and applications of WSNs have spread from the military domain into civilian domains to perform important functions such as security surveillance, fire protection, and monitoring of environmental conditions, medical patients, forest resources, and wildlife habitats, etc. These potential applications of WSNs are at an early stage of development, and much research remains to be done to make the widespread deployment of WSNs commercially viable.

This research is intended to advance the frontiers of WSN research by developing techniques that enhance the performance and usefulness of WSNs. These techniques address the problems of efficiently and reliably collecting, processing, transmitting, receiving and routing sensor data from a collection of sensor nodes to the intended data sinks. Low power consumption of sensor nodes is paramount to enable a long operating lifetime for distributed sensor networks. We develop practical distributed localization techniques that leverage the precise positioning of a small subset of all sensor nodes to allow other sensor nodes to accurately determine their positions, and energy-efficient geographical routing techniques based on the accurate positioning information.

Adaptive Security Architectures, Algorithms, and Protocols for Wireless Sensor Networks

Wireless sensor networks meet several operational challenges, such as energy efficiency in terms of maximizing the lifetime of sensor networks; scalability to a large number (thousands to millions) of nodes; survivability in certain environments where sensors are subject to compromise, capture, and manipulation by adversaries; support for dynamic addition/removal of sensors; and robustness to spontaneous interferences, collisions, and packet losses. Moreover, they are vulnerable to serious security attacks.

Different from the wired counterparts, sensor networks do not require any physical contact for communication, and hence, an adversary with a simple radio receiver/transmitter can easily eavesdrop conversation, inject/modify packets, and mount denial-of-service (DoS) attack.

Considering the network scale, the highly constrained system resource, and the fact that sensor networks are often deployed in unattended and hostile environments, we set the research objective as to develop efficient and scalable rekeying protocols with autonomous and adaptive capabilities for defending against node compromises in unattended sensor networks. This research will provide fundamental security services covering key management, authentication, compromise detection, and revocation. These services are essential for the successful deployment of sensor networks. Finally, the proposed protocols shall be evaluated in terms of security level, resource efficiency and scalability by theoretical analysis and simulations.

Modeling and Performance Evaluation of Cognitive Radio Networks

With the emergence of a variety of wireless multimedia applications, most of the usable radio spectrum has been densely allocated, which leads to the problem of spectrum scarcity worldwide. However, extensive measurement studies have indicated that the prime radio spectrum experiences significantly low utilization efficiency because of the current static spectrum allocation policy. Sparked by recent advances in cognitive radios, a new communication paradigm presents a possible solution to the spectrum inefficiency problem, which allows secondary users equipped with cognitive radios to opportunistically access unoccupied bands of licensed spectrum while limiting the interference perceived by the primary users. Such networking paradigm is referred to as Cognitive Radio Networks (CRNs). In this research, we studied the joint resource allocation schemes in cognitive femtocell networks.

New Models of Grid and Ubiquitous Computing for Image Processing

The main purpose of this research is to explore new software models/toolkits, named Ubiquitous Multi-Processor (UMP) system, to support distributed application development over the emerging ubiquitous/pervasive computing environment, such as ubiquitous computing, Peer-to-Peer (P2P) computing, and mobile computing environments. In the proposed application scenario, there are many PCs equipped with some UMPs. These PCs are distributed over different domains (each PC belongs and only belongs to one domain). There also has a resource router in each domain taking charge of UMP management request processing.

In the system, the behaviors of UMPs are controlled by corresponding resource router. Once it registers to the resource router successfully, a UMP will listen and accept for the task scheduled by the resource router. the UMP will also update it status information to the resource router when a task is finished.

To support mobile computing environments, the resource router should be aware of the location of mobile users and be able to locate available UMPs from the nearest domain, so as to reduce the communication cost for the request.

Refereed Journal Papers


Feilong Tang, Ilsun You, Minyi Guo, and Song Guo. Context-aware Workflow Management for Intelligent Navigation Applications in Pervasive Environments. Intelligent Automation and Soft Computing, 16(4):605-619, 2010.

Pervasive computing is a user-centric distributed computing paradigm, allowing users to access their preferred services even while moving around. To make this vision a reality, context-aware workflow management is one of key issues because the context of pervasive applications is changing instantly. In this paper, we propose a context model for intelligent navigation applications and then present a context-aware workflow management algorithm (CAWM) which can dynamically adjust workflow execution behaviours based on current context information. The correctness of the CAWM algorithm has been also verified theoretically by formulating it as a Petri-net model. Furthermore, the proposed context model and workflow management algorithm can apply to other applications by simply revising the corresponding context structures only.


Deze Zeng, Song Guo, and Victor Leung. The Exploration of Network Coding in IEEE 802.15.4 Networks. International Journal of Digital Multimedia Broadcasting, 2010.

Wireless Personal Area Networks (WPANs) are getting popular in a variety of fields such as smart home, office automation, e-healthcare, etc. In WPANs, most devices are considerably energy constrained, so the communication protocol should be energy efficient. The IEEE 802.15.4 is designed as a standard protocol for low power, low data rate, low complexity and short range connections in WPANs. The standard supports allocating several number of collision-free Guarantee Time Slots (GTSs) within a superframe for some time-critical transmissions. Recently, COPE was proposed as a promising network coding architecture to essentially improve the throughput of wireless networks. In this paper, we exploit the network coding technique at coordinators to improve energy efficiency of the WPAN. Some related practical issues, such as GTS allocation and multicast, are also discussed in order to exploit the network coding opportunities efficiently. Since the coding opportunities are mostly exploited, our proposal achieves both higher energy efficiency and throughput performance than the original IEEE 802.15.4.


Song Guo and Victor Leung. Exact and Performance-Guaranteed Multicast Algorithms for Lifetime Optimization in WANETs. Wiley Networks, 55(3):287-297, May 2010.

We consider the problem of maximizing the lifetime of a given multicast connection in wireless networks that use directional antennas and have limited energy resources. We provide a globally optimal solution to this problem by developing a general MILP formulation that can apply to many directional antenna models, some of which are not supported by the existing formulations. We also investigate the theoretical performance of a well-known heuristic algorithm for this optimization problem in terms of its approximation ratio. We use a graph theoretic approach, for the first time, to derive an upper bound on its approximation ratio in an analytical expression and discover that it is a constant-factor approximation algorithm.


Feilong Tang, Ilsun You, and Song Guo Minyi Guo. A Shadow-like Task Migration Based on Context Semantics for Mobile and Pervasive Environments. Computing and Informatics, 2010.

Pervasive computing is a user-centric mobile computing paradigm, in which tasks should be migrated over diérent platforms in a shadow-like way when users move around. In this paper, we propose a context-sensitive task migration model that recovers program states and rebinds resources for task migrations based on context semantics through inserting resource description and state description sections in source programs. Based on our model, we design and develop a task migration framework xMozart which extends the Mozart platform in terms of context awareness. Our approach can recover task states and rebind resources in the context-aware way, as well as support multi-modality I/O interactions. The extensive experiments demonstrate that our approach can migrate tasks by resuming them from the last broken points like shadows moving along with the users.


Song Guo and Victor Leung. Distributed Approximation Algorithms for Longest-lived Multicast in WANETs with Directional Antennas. IEEE Transactions on Wireless Communications, 9(7):2227-2237, July 2010.

We consider the lifetime optimization problem for multicasting in wireless ad hoc networks, in which each node is equipped with a directional antenna and has limited energy supplies. Several distributed algorithms proposed recently are especially beneficial to a resource-constrained wireless ad hoc network. In this paper, we propose a new distributed algorithm and investigate its theoretical performance compared to existing distributed algorithms. We use a graph theoretic approach to obtain the upper bound of the approximation ratio for a group of distributed algorithms. In particular, the derived upper bound in a closed form for each algorithm provides a sufficient condition to determine if the obtained solutions can reach optimum. Both theoretical and experimental performance analysis show that the new algorithm outperforms other proposals in terms of providing long-lived multicast tree.


Long Zheng, Kaoru Ota, Hai Jin, and Song Guo. Energy Efficiency of a Multi-Core Processor by Tag Reduction. Journal of Computer Science and Technology, 2010.

We consider the energy saving problem for caches on a multi-core processor. In the previous research on low power processors, there are various methods to reduce power dissipation. Tag reduction is one of them. This paper extends the tag reduction technique on a single-core processor to a multi-core processor and investigates the potential of energy saving for multi-core processors. We formulate our approach as an equivalent problem which is to find an assignment of the whole instruction pages in the physical memory to a set of cores such that the tag-reduction conflicts for each core can be mostly avoided or reduced. We then propose three algorithms using different heuristics for this assignment problem. We provide convincing experimental results, by collecting data from a real operating system instead of the traditional way using a processor simulator which cannot simulate operating system functions and the full memory hierarchy. Experimental results show that our proposed algorithms can save total energy up to 83.93% on an 8-core processor and 76.16% on a 4-core processor in average compared to the one that the tag-reduction is not used for. They also significantly outperform the tag reduction based algorithm on single-core processor.


Feilong Tang, Ilsun You, Song Guo, and Minyi Guo. A Chain-Cluster Based Routing Algorithm for Wireless Sensor Networks. Journal of Intelligent Manufacturing, 6(1):65-83, 2010.

Wireless sensor network (WSN) is an emerging technology for information gathering. Routing for WSNs is different from that for traditional wireless networks and ad hoc networks due to the energy constraint of sensor nodes so that saving energy becomes the most important goal of various routing algorithms for WSNs. For this purpose, a cluster based routing algorithm LEACH (low energy adaptive clustering hierarchy) divides a sensor network into a set of clusters and randomly votes the heads so that the energy load can be evenly distributed among the sensor nodes. Periodically voting cluster heads in LEACH, however, consumes much energy and other resources. PEGASIS (power-efficient gathering in sensor information systems) consumes less energy per round than LEACH by chain based routing, but it causes a longer delay for data transmission. In this paper, we propose a routing algorithm CCM (Chain-Cluster based Mixed routing), which makes full use of the advantages of LEACH and PEGASIS. CCM divides a WSN into a few chains and runs in two stages. In the first stage, sensor nodes in each chain transmit data to their own chain head node in parallel, using the improved chain routing protocol. In the second stage, all chain head nodes self-organize as a cluster, where they transmit fused data to a voted cluster head using cluster based routing. Experimental results demonstrate that our CCM algorithm outperforms both LEACH and PEGASIS in terms of the product of consumed energy and delay (i.e., energy terms of the product of consumed energy and delay (i.e., energy × delay). delay).


Song Guo and Victor Leung. A Distributed Algorithm for Min-Max Tree and Max-Min Cut Problems in Communication Networks. IEEE/ACM Transactions on Networking, 18(4):1067-1076, August 2010.

We consider the problem of finding a multicast tree rooted at the source node and including all the destination nodes such that the maximum weight of the tree arcs is minimized. It is of paramount importance for many optimization problems, e.g., the maximum-lifetime multicast problem in multihop wireless networks, in the data networking community. We explore some important properties of this problem from a graph theory perspective and obtain a min-max-tree max-min-cut theorem, which provides a unified explanation for some important while separated results in the recent literature. We also apply the theorem to derive an algorithm that can construct a global optimal min-max multicast tree in a distributed fashion. In random networks with n nodes and m arcs, our theoretical analysis shows that the expected communication complexity of our distributed algorithm is in the order of O(m). Specifically, the average number of messages is 2(n − 1 − γ) − 2ln(n − 1) + m at most, in which γ is the Euler constant. To our best knowledge, this is the first contribution that possesses the distributed and scalable properties for the min-max multicast problem, and is especially desirable to the large-scale resource-limited multihop wireless networks, like sensor networks.


Feilong Tang, Ilsun You, Cho-Li Wang, and Song Guo. A Pipeline-based Approach for Long Transaction Processing in Web Service Environment. International Journal of Web and Grid Services, 2010.

In web service environments, long transactions need to lock resources - often database services - for a long time during their long execution duration. This would bring down the performance of transaction processing systems. The transaction compensation is a feasible solution through allowing sub-transactions to independently commit, however, it is not able to speed up the transaction processing. This paper proposes a novel pipeline-based transaction processing (PLbTP) model for Serial Long Transactions (SLTs), which parallelises the transaction processing to reduce the transaction execution duration. Furthermore, we design a time-stampbased deadlock prevention mechanism for the control of multiple concurrent transactions. The simulation results demonstrate that our approach can significantly improve performance of SLTs without the aid of compensating transactions.


Feilong Tang, Minyi Guo, Song Guo, and Shui Yu. Service-Oriented Wireless Sensor Networks and An Energy-Aware Mesh Routing Algorithm. Ad Hoc & Sensor Wireless Networks, 2010.

Service-oriented wireless sensor networks (WSNs) are being paid more and more attention because service computing hides complexity of WSNs and enables simple and transparent access to individual sensor nodes. Existing WSNs mainly use IEEE 802.15.4 as their communication specification, however, this protocol suite cannot support IP-based routing and service-oriented access because it only specifies a set of physical- and MAC-layer protocols. For inosculating WSNs with IP networks, IEEE proposed a 6LoWPAN (IPv6 over LoW Power wireless Area Networks) as the adaptation layer between IP and MAC layers. However, it is still a challenging task how to discover and manage sensor resources, guarantee the security of WSNs and route messages over resource-restricted sensor nodes. This paper is set to address such three key issues. Firstly, we propose a service-oriented WSN architectural model based on 6LoWPAN and design a lightweight service middleware SOWAM (service-oriented WSN architecture middleware), where each sensor node provides a collection of services and is managed by our SOWAM. Secondly, we develop a security mechanism for the authentication and secure connection among users and sensor nodes. Finally, we propose an energy-aware mesh routing protocol (EAMR) for message transmission in a WSN with multiple mobile sinks, aiming at prolonging the lifetime of WSNs as long as possible. In our EAMR, sensor nodes with the residual energy lower than a threshold do not forward messages for other nodes until the threshold is leveled down. As a result, the energy consumption is evened over sensor nodes significantly. The experimental results demonstrate the feasibility of our service-oriented approach and lightweight middleware SOWAM, as well as the effectiveness of our routing algorithm EAMR.

Refereed Proceedings Papers


Song Guo and Victor Leung. A Compromise-Resilient Group Rekeying Scheme for Hierarchical Wireless Sensor Networks. In IEEE Wireless Communications and Networking Conference (WCNC), April 2010.

The wireless sensor networks (WSNs) are normally operated in unattended, harsh, or hostile environment. The adversaries may easily compromise some sensor nodes and abuse their shared keys to inject false sensing reports or modify the reports sent by other nodes. Many applications in WSNs require secure group communications, which are supported by group keys. Once a malicious node is detected in the group, the group key should be renewed immediately for the network security. Some strategies have been proposed to develop the group rekeying protocol, but most existing schemes suffer the node capture attack. To conquer this problem, we propose a new compromise-resilient group rekeying scheme for hierarchical WSNs in this paper. Compared with existing schemes, our rekeying method possesses the following features: (1) it is robust to the node capture attack, (2) it supports both forward secrecy and backward secrecy, and (3) it has low communication and storage overhead, which are particularly beneficial to the resource-constrained large-scale sensor networks.


Song Guo, Victor Leung, and Zhuzhong Qian. A Permutation-Based Multi-Polynomial Scheme for Pairwise Key Establishment in Sensor Networks. In IEEE International Conference on Communications (ICC), May 2010.

The wireless sensor networks (WSNs) are normally operated in unattended, harsh, or hostile environment. Some strategies have been proposed to establish pairwise keys to protect the sensitive data and the sensor readings, but most existing schemes either suffer the large-scale node capture attacks, or cannot provide full and direct key establishment. In this paper, we present a permutation-based multi-polynomial scheme for pairwise key establishment in wireless sensor networks. This scheme is highly robust to the large-scale node capture attacks. Even after a large number of nodes have been compromised, the pairwise keys shared by non-compromised nodes remain secure. It also guarantees that any two nodes can directly establish a pairwise key without exposing any secret to other nodes. This full and direct key establishment features enable our scheme every adaptive to support node addition and mobility, which are particularly beneficial to the real-world applications. Our performance analysis also shows that the proposed scheme incurs low communication, storage, and computation overhead.


Deze Zeng and Song Guo. An Energy-Aware MAC Protocol for Wireless Personal Area Networks. In IEEE International Symposium on Aware Computing (ISAC), November 2010.

Wireless Personal Area Networks (WPANs) are getting popular in a variety of fields such as home/office automation, e-healthcare, etc. In WPANs, most devices are considerably energy constrained, so the communication protocol should be energy efficient. The IEEE 802.15.4 is designed as a standard protocol for low power, low data rate, low complexity and short range connections in WPANs. The standard supports allocating several number of collision-free Guarantee Time Slots (GTSs) within a superframe for some time-critical transmissions. Recently, COPE was proposed as a promising network coding architecture to essentially improve the throughput of wireless networks. In this paper, we exploit the network coding technique to improve energy efficiency of the WPAN coordinators.We make the WPAN coordi nators network coding aware. Some related practical issues, such as GTS allocation and multicast, are also discussed in order to exploit the network coding opportunities efficiently. Since the coding opportunities are mostly exploited, our proposal achieves both higher energy efficiency and throughput performance than the original IEEE 802.15.4.


Quan Chen, Daqiang Zhang, Minyi Guo, Qianni Deng, and Song Guo. SAMR: A Self-adaptive Map-Reduce Scheduling Algorithm in Heterogeneous Environment. In IEEE International Conference on Computer and Information Technology (CIT), June 2010.

Hadoop is seriously limited by its MapReduce scheduler which does not scale well in heterogeneous environment. Heterogenous environment is characterized by various devices which vary greatly with respect to the capacities of computation and communication, architectures, memorizes and power. As an important extension of Hadoop, LATE MapReduce scheduling algorithm takes heterogeneous environment into consideration. However, it falls short of solving the crucial problem poor performance due to the static manner in which it computes progress of tasks. Consequently, neither Hadoop nor LATE schedulers are desirable in heterogeneous environment. To this end, we propose SAMR: a Self-Adaptive MapReduce scheduling algorithm, which calculates progress of tasks dynamically and adapts to the continuously varying environment automatically. When a job is committed, SAMR splits the job into lots of fine-grained map and reduce tasks, then assigns them to a series of nodes. Meanwhile, it reads historical information which stored on every node and updated after every execution. Then, SAMR adjusts time weight of each stage of map and reduce tasks according to the historical information respectively. Thus, it gets the progress of each task accurately and finds which tasks need backup tasks. What's more, it identifies slow nodes and classifies them into the sets of slow nodes dynamically. According to the information of these slow nodes, SAMR will not launch backup tasks on them, ensuring the backup tasks will not be slow tasks any more. It gets the final results of the fine-grained tasks when either slow tasks or backup tasks finish first. The proposed algorithm is evaluated by extensive experiments over various heterogeneous environment. Experimental results show that SAMR significantly decreases the time of execution up to 25% compared with Hadoop's scheduler and up to 14% compared with LATE scheduler.


Long Zheng, Hai Jin, Minyi Guo, and Song Guo. Core-Degree Based Tag Reduction on Chip Multiprocessor to Balance Energy Saving and Performance. In IFIP International Conference on Network and Parallel Computing (NPC), September 2010.

Tag reduction is an approach to save energy of the cache system in a processor. Our previous work described that it can save more energy on a Chip Multiprocessor (CMP) than on a single-core processor. In this paper, we further investigate the problem on balancing energy saving and performance overhead when tag reduction is used for the low power Chip Multiprocessor (CMP). We first introduce the core degree concept which is defined as the number of cores that tag reduction can use for each thread. We then propose a core degree based tag approach that is to optimize the core degree such that the best balance of energy and performance can be achieved. In particular, as the basis for such optimization, the theoretical upper bounds of the energy savings and performance overhead are decided as function of the core degree. In our experiments, we use a 16-core CMP for example. In order to obtain the energy consumption and performance overhead with various core degrees, we construct an experimental environment, which is based on the Linux operating system. With the experimental environment, benchmarks of SPEC CPU2006 are used to evaluate our core degree based tag reduction. Finally, the experimental results show that the most desired balance of energy saving and performance overhead is achieved when core degree is set to 6.


Feilong Tang, Ilsun You, Minyi Guo, and Song Guo. GridTDK: A Grid Transaction Development Kit. In International Conference on NetworkBased Information Systems (NBiS), September 2010.

Grid computing assists people to accomplish collaborative tasks and hides complex processes from them. In such environments, transaction management is one of core technologies, guaranteeing the system consistency in face of various failures. In this paper, we proposes a Grid transaction development kit (GridTDK) for programming reliable applications. GridTDK has the three advantages. Firstly, it separates the transaction manager with transaction coordination algorithms so that it can coordinate short-lived, long-lived and real-time transactions in an uniform way. Secondly, GridTDK can dynamically generate compensating transactions during the execution of long-lived transactions. Finally, it provides the programming interfaces similar to traditional distributed transactions. We evaluate the feasibility and effectiveness of GridTDK through a general application.


Deze Zeng, Song Guo, Zhuo Li, and Sanglu Lu. Performance Evaluation of Network Coding in Disruption Tolerant Networks. In ACM Asia-Pacific Symposium on Internetware (Internetware), November 2010.

Delay/Disruptive Tolerant Network (DTN) differs from the traditional networks in that it has no continuous or contemporaneous connections but only intermittent connections among wireless nodes and thus it is viewed as an opportunistic networks. DTNs emerge as a good alternative to provide services to a variety of applications in highly challenged environments. However, the characteristics of DTNs make existing solutions infeasible to be applied directly and new solutions are required to be explored, such as multicast which has been extensively studied before in internet and mobile ad hoc networks. Network coding has been proved been proved as an efficient way to improve the performance of multicast in traditional networks. In this paper, we use simulations to study how multicast with network coding performs in DTNs in terms of delivery delay under various application requirements (i.e., the amount of content to distribute and the number of multicast group members) and the network settings (i.e., the popularity of the network and the contact rate). Some empirical results are provided in this paper as well.


Kaoru Ota, Mianxiong Dong, Junbo Wang, Song Guo, Zixue Cheng, and Minyi Guo. Dynamic Itinerary Planning for Mobile Agents with a ContentSpecific Approach in Wireless Sensor Networks. In IEEE Vehicular Technology Conference (VTC), September 2010.

We study data fusion in sensor networks using mobile agents (MAs),which are capable of saving energy of sensor nodes and performing advanced computation functions based on the requests of various applications. Research on MAs still remains unfledged in development of application-oriented data fusion, which is highly desired in wireless sensor networks (WSNs) deployed in recent days for environmental and disaster monitoring. In this paper, we propose a dynamic itinerary planning for MAs (DIPMA) to collect data from sensor networks with an application-oriented approach. In particular, the DIPMA algorithm is applied to the data collection for frost prediction which is a real-world application in agriculture using next-generation sensor networks. The performance of the DIPMA is evaluated by simulations and the experimental results show that the total execution time of MA can be reduced significantly with our approach while sound prediction accuracy is maintained.


Peng Li and Song Guo. Energy Minimization in Speculative Parallelization Using Dynamic Voltage Scaling on Multicore Systems. In International Symposium on Parallel and Distributed Computing (ISPDC), July 2010.

Thread-Level Speculation (TLS) has shown great promise as an automatic parallelization technique to achieve high level performance by partitioning a sequential program into threads, which are expected to be optimistically executed in parallel. In this paper, we propose a load-balancing approach to save energy using dynamic voltage scaling. By scaling the voltage of processors running short threads, energy consumption on these processors can be reduced while keeping a similar speedup of the overall system. Two voltage selection strategies have been investigated. With the assistance of some profiling tools, we propose a static voltage selection algorithm that can minimize energy consumption without degrading the parallelism provided by the pure TLS. The other dynamic algorithm selects voltage for each thread with prediction during the execution. Our experimental results show that its energy consumption is reduced to 78.8% and execution time is stretched to 1.07 times, on average, of the pure TLS in a 16-core CMP processor.


Mianxiong Dong, Long Zheng, Song Guo, and Minyi Guo. A Probabilistic-approach based Resource Allocation Algorithm in Pervasive Computing Systems. In IEEE International Conference on Computer Application and System Modeling (ICCASM), October 2010.

Ubiquitous technologies are indispensable for modernizing human daily life more and more. However, the technologies are not easily widespread everywhere in our world through infrastructures and other related techniques. We have worked on a project to meet these challenges with a goal to construct a framework for the coming ubiquitous society. In our previous works, we have proposed UMP-PerComp, a Ubiquitous Multiprocessor-based pipeline Processing architecture, to support development of powerful and pervasive applications. In this paper, we propose an optimized algorithm for the UMP system to improve resource allocation executed by one kind of processing nodes called the Resource Router (RR). Using the optimized algorithm, the RR can effectively find a node in the idle state, which actually processes a task assigned by the RR. As a result, the RR saves the time to search for an idle node so that total performance can be improved. Finally, we evaluate the optimized algorithm with probability analyses to show effectiveness more than the previous algorithm we used.


Long Zheng, Mianxiong Dong, Minyi Guo, and Song Guo. Exploring the Limits of Tag Reduction for Energy Saving on a Multi-core Processor. In IEEE International Symposium on Embedded Multicore Systems-on-chip (MCSoC), September 2010.

Saving energy usually leads to performance degradation. We explore the theoretical limits of tag reduction on a multi-core processor with guaranteed performance effect. In our previous work, tag reduction is applied to multi-core processors and shows significant energy savings. In this paper, we analyze the performance overhead caused by tag reduction on the multi-core processor. Meanwhile, we have found out that when tag reduction is used on multi-core processors, the number of cores is the key factor that affects both energy consumption and performance overhead. More specifically, as the number of cores varies incrementally, energy saving increases, while performance degrades. Tag reduction has limits that are represented by the number of cores to achieve maximal energy saving with performance overhead constraints. In order to derive the limits, we study the relationship between energy consumption and performance overhead by formulating them into several equations. In our experiment, we modify the Linux kernel and implement some modules to collect the experimental data such that we can evaluate 22 benchmarks from SPEC CPU2006. A scalable multi-core processor platform has also been constructed to find the limits of tag reduction on the multi-core processor. The analysis of experimental results shows that when the number of cores is 6, energy saving by tag reduction reaches the limits with performance constraints.


Peng Li, Song Guo, Hai Jin, and Victor Leung. Maximum Lifetime Broadcast and Multicast Routing in Unreliable Wireless Ad-hoc Networks. In IEEE Global Telecommunications Conference (Globecom), December 2010.

The reliable broadcast and multicast lifetime maximization problems in energyconstrained wireless ad-hoc networks are considered in this paper. In packet lossfree networks, the optimal solution of lifetime maximization problem can be easily obtained by tree based algorithms. In unreliable networks, we formulate them as min-max tree problems. A link quality-aware heuristic algorithm called MLRBT (Maximum Lifetime Reliable Broadcast Tree) is proposed to build a broadcast tree that maximizes the network lifetime. The reliable multicast lifetime maximization problem can be solved as well by pruning the broadcast tree produced by the MLRBT algorithm. Simulation results show that the proposed algorithms can significantly increase the network lifetime compared with the traditional algorithms under various distribution of unreliable communication links.


Deze Zeng, Song Guo, Hai Jin, and Shui Yu. On the Maximum Throughput of Two-Hop Wireless Network Coding. In IEEE Wireless Communications and Networking Conference (WCNC), March 2011.

Network coding has shown the promise of significant throughput improvement. In this paper, we study the throughput of two-hop wireless network coding and explore how the maximum throughput can be achieved under a random medium access scheme. Unlike previous studies, we consider a more practical network where the structure of overhearing status between the intended receivers and the transmitters is arbitrary. We make a formal analysis on the network throughput using network coding upon the concept of network coding cliques (NCCs). The analysis shows that the maximum normalized throughput, subject to fairness requirement, is n n+m , where n is the number of transmitters and m is the number of NCCs in a 2-hop wireless network. We have also found that this maximum throughput can be achieved under a random medium access scheme when the medium access priority of the relay node is equal to the number of NCCs in the network. Our theoretical findings have been validated by simulation as well.


Tao Hu, Minyi Guo, Song Guo, and Hirokazu Ozaki. Minimizing the Energy Consumption of Behavior-Oriented Parallelization. In IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA), September 2010.

Although the reliability of the composition of web services has attracted much research works about it, but an important facet of it C MTTF (Meantime to Failure) has not been given enough considerations. The research presented in this paper intends to fill this gap by illustrating on an example of composite web service how the redundant system works and what kinds of practical results can be derived. The main contributions of this work includes: First, provide the concept of MTTF of composite web service, which is little concerned in previous works. Second, describing the calculation method of MTTF of composite web based on the workflow composition pattern. Third, presents the quantitative analysis of MTTF of composite web service for non-redundant services, part-redundant services, and all-redundant services based system. And we show that by an experiment, to achieve the higher reliability of a system, it is necessary to decrease the failure rate and increase the repair rate in addition to providing redundant system.



Song Guo. Joint Research Fund of Olympus Corporation, 2010.


Song Guo. JSPS Grant-in-Aid for Scientific Research, 2008 - 2010. Song Guo.


Song Guo. Grant-in-Aid for JSPS Fellows, 2009 - 2011.

Academic Activities


K.Otsuyama, Feb 2010.

4th ISPJ Tohoku branch workshop section chair


Song Guo, 2001 -. Member, ACM, IEEE, IEEE ComSoc


Song Guo, 2010 -. Editor, Ad Hoc & Sensor Wireless Networks


Song Guo, 2010 -. Associate Editors-in-Chief, International Journal of Digital Content Technology and its Applications


Song Guo, 2010 -. Editor, Advances in Network and Communication


Song Guo, 2004 -.

Technical Committee, IEEE Ad Hoc and Sensor Networks Technical Committee


Song Guo, 2010.

Member of Program Committee:

IEEE Wireless Communications and Networking Conference

IEEE Symposium on Personal, Indoor and Mobile Radio Communications

IEEE Conference on Ubiquitous Intelligence and Computing

International Conference on Information Systems, Technology and Management

IEEE International Symposium on Embedded Multicore Systems-on-chip

International Workshop on Localized Algorithms and Protocols for WSNs

International Workshop on Advances in Emerging Wireless Networks and Systems

IEEE International Conference on Embedded Software and Systems

International Conference on Network-Based Information Systems

International Conf. on Ubiquitous Information TEchnologies & Applications

International Symposium on Aware Computing

International Workshop on Peer-to-Peer Networking

IFIP Conference on Embedded and Ubiquitous Computing

IEEE Conference on Computer and Information Science

IEEE International Workshop on Wireless Network Algorithm and Theory

IEEE/IFIP Symposium on Trust, Security and Privacy for Pervasive Applications


Song Guo, 2010.

Guest Editor, Peer-to-Peer Networking and Application


Song Guo, 2006 -.

Editor, the Open Information Systems Journal


Song Guo, 2010.

Reviewing Activities for Archived Journals:

IEEE Communications Letters

IEEE Transactions on Wireless Communications

Computer Communications

IET Communications

Ad Hoc & Sensor Wireless Networks

International Journal of Advancements in Computing Technology

International Journal of Ad Hoc and Ubiquitous Computing

Wireless Communications and Mobile Computing


Song Guo, 2010.

Program Vice-Chair, International Conference on Parallel and Distributed Computing, Applications and Technologies


Song Guo, 2010.

Publicity Co-Chair, IEEE International Conference on Embedded Software and Systems


Song Guo, 2010.

Technical Committee, IEEE Wireless Communications Technical Committee

Ph.D., Master and Graduation Theses


Fumihide Hamada. Graduation Thesis:The Rearrangement and Evaluation of Small World Networks, School of Computer Science and Engineering, March 2011.

Thesis Adviser: K. Otsuyama


Haruhisa Abe. Graduation Thesis: Comparison and Verification of network growth models on Social Network Service, School of Computer Science and Engineering, March 2011.

Thesis Adviser: K. Otsuyama


Takahiro Namatame. Graduation Thesis: Development of a Information Search System for Local Agricultural Production, School of Computer Science and Engineering, March 2011.

Thesis Adviser: K. Otsuyama


Hideaki Suzuki. Graduation Thesis: Development of the system that analyzes the web usability, School of Computer Science and Engineering, March 2011.

Thesis Adviser: K. Otsuyama


Yurika Sakai. Graduation Thesis: Peformance improvement of sort program with GPGPU, School of Computer Science and Engineering, March 2011.

Thesis Adviser: K. Otsuyama



H.Abe and K.Otsuyama. Comparison and Verification of Network Growth Models on Social Networking Service, 2010. 4th ISPJ Tohoku branch workshop


F.Hamada and K.Otsuyama. The Rearrangement and Evaluation of Small World Networks, 2010.

4th ISPJ Tohoku branch workshop