Performance Evaluation Laboratory

Minyi Guo Professor	Kouhei Otsuyama Assistant Professor	Song Guo Assistant Professor	Feilong Tang Visiting Researcher

The laboratory mission in the broad sense is to contribute to: Power-Aware and High Performance Instruction Scheduling for Embedded Systems Energy-efficient and Secure Computing in Distributed Wireless Sensor Networks New Models of Grid and Ubiquitous Computing for Image Processing Power-Aware and High Performance Instruction Scheduling for embedded systems In most of compilers, the goal of traditional instruction scheduling algorithms is to improve performance in terms of execution time. This can be done by some well-known ways such as superblock scheduling, hyperblock scheduling, and treegion scheduling. These scheduling strategies focus mainly on increasing performance through increasing the amount of instruction-level parallelism in program code. However, in VLIW (very long instruction word) architectures, an instruction word consists of a variable number of individual instructions. Therefore the step power and peak power consumption vary significantly depending on the parallel schedule generated by compiler. Power variation reduction without losing execution speed is an important scheduling constraint for embedded VLIW architectures. In this research, we studied some power-aware scheduling strategies for VLIW processors. These scheduling methods include low power scheduling for basic blocks with integer programming Modulo and Software Pipelining for loops Register allocation and cache reuse for power reduction. Energy-efficient and Secure Computing in Distributed Wireless Sensor Net- works Recently, research on wireless sensor networks (WSNs) has intensied, and applications of WSNs have spread from the military domain into civilian domains to perform important functions such as security surveillance, re 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 and secure 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 secure and energy-efficient efficient geographical routing techniques based on the accurate positioning information. 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

[minyi-01:2008]	Kaikai Chi, Xiaohong Jiang, Susumu Horiguchi, and Minyi Guo. Topology Design of Network-Coding-Based Multicast Networks. IEEE Transactions on Parallel and Distributed Systems, 19(5):627–640, May 2008.
	It is anticipated that a large amount of multicast traffic needs to be supported in future communication networks. The network coding technique proposed recently is promising for establishing multicast connections with a significantly lower bandwidth requirement than that of traditional Steiner-tree-based multicast connections. How to design multicast network topologies with the consideration of efficiently supporting multicast by the network coding technique becomes an important issue now. It is notable, however, that the conventional algorithms for network topology design are mainly unicast-oriented, and they cannot be adopted directly for the efficient topology design of network-coding-based multicast networks by simply treating each multicast as multiple unicasts. In this paper, we consider for the first time the novel topology design problem of network-coding-based multicast networks. Based on the characteristics of multicast and network coding, we first formulate this problem as a mixed-integer nonlinear programming problem, which is NP-hard, and then propose two heuristic algorithms for it. The effectiveness of our heuristics is verified through simulation and comparison with the exhaustive search method. We demonstrate in this paper that, in the topology design of multicast networks, adopting the network coding technique to support multicast transmissions can significantly reduce the overall topology cost as compared to conventional unicast-oriented design and the Steiner-tree-based design.
[minyi-02:2008]	Weng-Long Chang, Ting-Ting Ren, Jun Luo, Mang Feng, Minyi Guo, and Kawuu Weicheng Lin. Quantum Algorithms for Biomolecular Solutions of the Satisfiability Problem on a Quantum Machine. IEEE TRANSACTIONS ON NANOBIOSCIENCE, 7(3):215–222, September 2008.
	In this paper, we demonstrate that the logic computation performed by the DNAbased algorithm for solving general cases of the satisfiability problem can be implemented more efficiently by our proposed quantum algorithm on the quantum machine proposed by Deutsch. To test our theory, we carry out a three-quantum bit nuclear magnetic resonance experiment for solving the simplest satisfiability problem.
[minyi-03:2008]	Mianxiong Dong, Kaoru Ota, Feilong Tang, Minyi Guo, and Zixue Cheng. Intelligence@Lab: A Smart Space for Researchers Based on Sensor Networks in Pervasive Computing Environment. International Journal of Smart Home, 2(3):19–36, July 2008.
	With the rapid progress on the Internet Technology, many projects have been proposed in terms of remote education system such asWBT (Web-Based Training) and E-learning. Such systems can help learners for studying by themselves based on their own learning history in a virtual world. However, learners usually spend time in the real world during studying, exercising, and the other activities. It seems the systems do not give enough support to learners in the real world. Ubiquitous technologies make it possible to provide services to learners anytime and anywhere in the real world. It means learners can receive more meticulous, individually-targeted support in ubiquitous environments. In this paper, we propose a ubiquitous environment to support college students, professors, and visitors in a laboratory to encourage positive research activities. Actions of people in the Ubiquitous Laboratory (U-Lab) are individually recorded by sensor networks and analyzed to provide suitable supports. Based on these collected information, U-Lab provides services such as to grasp a precise research progress and share research information among students and professors. We also propose a method to advise students to improve their research activities. As a case study, we implemented a ubiquitous corner (U-Corner) in order to prove our proposal is useful and practical.
[sguo-01:2008]	Song Guo, Minyi Guo, and Victor Leung. A Message Complexity Oriented Design of Distributed Algorithm for Long-lived Multicasting in Wireless Sensor Networks. International Journal on Sensor Networks, 6(3/4):180–190, 2009.
	We consider an optimization problem in wireless sensor networks (WSNs) that is to find a multicast tree rooted at the source node and including all the destination nodes such that the lifetime of the tree is maximized. While a recently proposed distributed algorithm for this problem guarantees to obtain optimal solutions, we show that its high message complexity may prevent such contribution from being practically used in resource-constrained WSNs. In this paper, we proposed a new distributed suboptimal algorithm that achieves a good balance on the algorithmoptimality and message complexity. In particular, we prove that it has a linearmessage complexity. The tradeoff between algorithm sub-optimality and message complexity is also studied by simulations.
[sguo-02:2008]	Minyi Guo, Elizabeth Olule, GuojunWang, and Song Guo. Designing Energy Efficient Target Tracking Protocol with Quality Monitoring in Wireless Sensor Networks. Journal of Supercomputing, 51(2):131–148, 2010.
	Target tracking is one application of wireless sensor networks and energy efficient target tracking algorithms that can be used for accurate tracking are highly desired. In order to achieve energy savings, we focus on reducing energy usage by limiting the number of sensors used to track a target through monitoring their data quality and by limiting the amount of data being sent to the cluster head. We propose an energy efficient target tracking protocol that uses two algorithms to accomplish this goal. Simulation studies show that the network lifetime is extended up to 35effect on target tracking accuracy is not too negative.
[sguo-03:2007]	An-Ni Shen, Song Guo, and Victor Leung. A Flexible and Efficient Key Distribution Scheme for Renewable Wireless Sensor Networks. EURASIP Journal on Wireless Communications and Networking,Volume 2009 (2009), Article ID 240610, 9 pages, 2009.
	In this paper, we propose a new key distribution scheme for hierarchical WSNs with renewable network devices. Compared to some of the existing schemes, our key establishment methods possess the following features that are particularly beneficial to the resource-constrained large-scale WSNs: (1) robustness to the node capture attack, (2) flexibility for adding new network devices, (3) scalability in terms of storage cost, and (4) low communication overhead.
[sguo-04:2008]	Song Guo and Oliver Yang. A Framework for the Multicast Lifetime Maximization Problem in Energy-Constrained Wireless Ad-hoc Networks. ACM Wireless Networks Journal, 15(3):313–329, April 2009.
	We provide a globally optimal solution to the multicast lifetime maximization problem for a special case of using omni-directional antennas. This graph theoretic approach provides us insights into more general case of using directional antennas, and inspires us to produce a group of heuristic algorithms. Experimental results show that minimum total power consumption does not guarantee maximum lifetime for either broadcasting or multicasting, and our algorithms outperform other energy-aware multicast algorithms significantly in terms of multicast lifetime.
[sguo-05:2008]	Feilong Tang, Ilsun You, Minyi Guo, and Song Guo. Context-awareWorkflow 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.
[sguo-06:2008]	Song Guo and Oliver Yang. Maximizing Multicast Communication Lifetime in Wireless Mobile Ad Hoc Networks. IEEE Transactions on Vehicular Technology, 57(4):2414 – 2425, July 2008.
	Unlike most multicast algorithms that use centralized greedy algorithms to achieve maximum-lifetime in static ad hoc networks, we present two distributed multicast algorithms for the same optimization problem in mobile ad hoc networks. Our distributed algorithms also explore the localized operations to take the advantages of power saving offered by the wireless multicast advantage property in mobile networks. The extensive simulation results have shown that our algorithms outperform other proposals in terms of multicast lifetime under different node mobilities.
[sguo-07:2008]	An-Ni Shen, Song Guo, Hung Yu Chien, and Minyi Guo. A Scalable Key Pre-distribution Mechanism for Large-scale Wireless Sensor Networks. Wiley Journal of Concurrency and Computation: Practice and Experience, 21(10):1373–1387 2009.
	Many applications of wireless sensor network (WSN) require secure data communications, especially in a hostile environment. In order to protect the sensitive data and the sensor readings, secret keys should be used to encrypt the exchanged messages between communicating nodes. Traditional asymmetric key cryptosystems are infeasible in WSNs due to the extremely low capacity and constrained resources at each senor node. Recently proposed protocols are either vulnerable to the largescale node capture attacks or lack of performance scalability in terms of storage, communication and computation costs. To address these limitations, we study the key pre-distribution schemes in this paper and propose a new one with all of the following properties which are particularly beneficial to the large-scale resourceconstrained WSNs: (1) it completely defends against the node capture attacks, (2) it provides full connectivity of the network, and (3) it reduces the storage and communication overhead significantly compared to the other proposals.
[sguo-08:2008]	Mianxiong Dong, Long Zheng, Song Guo, and Minyi Guo. Improved Resource Allocation Algorithms for Practical Image Encoding in a Ubiquitous Computing Environment. Journal of Computers, 4(9):873–880, 2009.
	As a case study of the ubiquitous computing system, we have implemented a prototype for the JPEG encoding application. In order to achieve this eventual development in the real world, we studied resource allocation policies that can improve the overall performance of the system. In this paper, we consider those static and dynamic allocation approaches and then propose four different allocation algorithms. In particular, we extensively studied the dynamic allocation algorithms by exploring various cache policies which include disabled cache, unrestricted cache and restricted cache. Performance of these algorithms in large scale application scenario is also evaluated based on both the improved prototype and a simulation environment. The experimental results show a significant performance improvement achieved by the new proposed algorithms in terms of load balance, execution time, waiting time and execution efficiency.
[sguo-09:2008]	Song Guo and Victor Leung. Exact and Performance-Guaranteed Multicast Algorithms for Lifetime Optimization in WANETs. Wiley Networks, 2009.
	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.

Refereed Proceeding Papers

[minyi-04:2008, sguo-13:2008]	Mianxiong Dong, Gongwei Zhang, Kaoru Ota, Song Guo, and Minyi Guo. An Improved Design of the Ubiquitous Learning System Based on Sensor Networks. In Proceedings of the 5th IEEE/IFIP Interna- tional Conference On Embedded and Ubiquitous Computing (EUC 2008), pages 703–708, Shanghai, China, December 2008. IEEE Computer Press.
	With the great progress of information technologies, computers are embedded into everywhere to make our daily life convenient, efficient and invisible. In order to utilize this progress for learning, a scheduler system, a Ubiquitous Learning System (ULS) was proposed. ULS contributes a lot to improve student¨s learning efficiency. Yet improvement can still be made to the system by using sensor networks. In our new design, we embed various kinds of sensors, like temperature sensor, oxygen sensor, light sensor, into the environment. Based on the information collected by such sensors, decisions can be made by the control center to adjust the environment automatically for learner. Our research result reveals that the improved ULS not only benefited learners to acquire their learning habits but also improve their learning efficiency.
[minyi-05:2008, sguo-21:2008]	Mianxiong Dong, Song Guo, and Minyi Guo. Lifetime Approximation Schemes Allow Multicast Algorithm with Linear Message Complexity inWireless Sensor Networks. In Proceedings of 10th IEEE International Conference on High Performance Computing and Communications (HPCC 2008), pages 532–539, Dalian, China, September 2008. IEEE, IEEE Computer Press.
	We consider an optimization problem in wireless sensor networks (WSNs) that is to find a multicast tree with maximum lifetime. While a recently proposed distributed algorithm for this problem guarantees to obtain optimal solutions, its high message complexity may prevent such contribution from being practically used in resourceconstrained WSNs. In this paper, we proposed a new distributed algorithm that achieves a good balance on the algorithm optimality and message complexity. We use a graph theoretical approach, by the first time, to derive the bounds of both approximation ratio and message complexity in an analytical expression for this algorithm. The theoretical analysis on the tradeoff between these two performance metrics is also validated by our simulation studies.
[minyi-06:2008, sguo-24:2008]	Song Guo, Minyi Guo, Victor C, and M. Leung. A Performance Guaranteed Distributed Multicast Algorithm for Long-Lived Directional Communications inWANETs. In Proceedings of the 15th International Conference on High Performance Computing (HiPC 2008), Lecture Notes in Computer Science 5374, pages 439–450, Bangalore, India, December 2008. Springer.
	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. In this paper, we propose a new distributed algorithm, whose performance in terms of providing long-lived multicast tree is guaranteed by our theoretical analysis. We prove that its approximation ratio is bounded by a finite number. In particular, the derived upper bound in a closed form shows that the algorithm can achieve global optimal in some cases. The real performance of this new proposed algorithm is also evaluated using simulation studies and the experimental results show that it outperforms other distributed algorithms.
minyi-07:2008, sguo-25:2008]	Mianxiong Dong, Minyi Guo, Long Zheng, and Song Guo. Performance Analysis of Resource Allocation Algorithms Using Cache Technology for Pervasive Computing System. In Proceedings of t9th International Conference for Young Computer Scientists (ICYCS 2008), pages 671–676, Zhang Jia Jie, China, November 2008. IEEE, IEEE Computer Press.
	With the great progress of the Information Technologies, micro-processors are embedded into everywhere to make our daily life convenient, efficient and comfortable. However, how to integrate distributed resources existing among heterogeneous devices to build pervasive applications that can constantly adapt to the highly dynamic computing environment is still a challenge. On our previous work, by analyzing the pipelining feature within a user task and exploiting the parallelism among the ubiquitous processors, we have proposed UMP-Percomp, which is a Ubiquitous Multiprocessor-based pipeline processing architecture to support high performance pervasive application development. As a case study of the UMP (Ubiquitous Multi- Processor) system, we have implemented a prototype system of the JPEG encoding. In this research, we have studied three different scheduling policies to the prototype system and proposed the best architecture of the UMP system. We have also introduced the cache technology to the proposed resource allocation algorithm. To prove our ideas, a simulation based system was implemented. The experience results revealed that the proposed algorithms made a significant progress over the existing solution.
[minyi-08:2008, sguo-26:2008]	Song Guo, Minyi Guo, and Victor C. M. Leung. A tradeoff analysis on message complexity and lifetime optimality for a distributed multicast algorithm in WSNs. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing (PODC 2008), page 433, Tronto, Canada, August 2008. ACM, ACM Press.
	We consider the lifetime maximization for multicast in wireless sensor networks (WSNs) and propose a new distributed algorithm that achieves a good balance on algorithm optimality and message complexity.
[minyi-09:2008]	Weng-Long Chang, Ting-Ting Ren, Jun Luo, Mang Feng, and Minyi Guo. Quantum algorithms for bio-molecular solutions to the satisfiability problem on a quantum computer. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2008), pages 1080–1088, Hong Kong, China, June 2008. IEEE.
	We demonstrate that the logic computation performed by the DNA-based algorithm for solving general cases of the satisfiability problem can be implemented by our proposed quantum algorithm on the quantum machine proposed by Deutsch. Moreover, we also prove that the logic computation by the bio-molecular operations proposed by Adleman can be implemented by quantum gates (for example, the Hadamard gate, NOT, CNOT, and CCNOT) on the quantum machine. Furthermore, those NP-complete problems solved on a bio-molecular computer are also solvable on a quantum computer. To test our theory, we carry out a three-qubit NMR experiment for solving the simplest satisfiability problem.
[minyi-10:2008]	Gongwei Zhang, Mianxiong Dong, Long Zheng, Deze Zeng, and Minyi Guo. An Improved Design for UMP (Ubiquitous Multi-processor) System. In Proceedings of IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA 2008), pages 540–546, Sydney, Australia, December 2008. IEEE, IEEE Computer Press.
	Recently, pervasive computing has become a very hot research field. Future Creation Lab., Olympus Corp. and the University of Aizu are working on this future technology to facilitate peoplepsilas everyday life. The system we have proposed is named UMP-Percomp, a ubiquitous multiprocessor-based pipeline processing architecture to support high performance pervasive application development. Until now, we have implemented a prototype system to evaluate the performance of the architecture. However, the structure of the prototype system has some limitations: lack of scalability, inefficient pipeline algorithm, and do not do anything if there is lack of available PEs. So we modify the design to change these disadvantages. We add a UDP server to each component to support scalability and component substitution. We design a parallel algorithm to maximum the usage of PEs, and we also consider the situation of lacking suitable PEs. Finally, we do an experiment on the new system to compare with the old system.
[sguo-10:2008]	An-Ni Shen, Song Guo, and Hung-Yu Chien. An Efficient and Scalable Key Distribution Mechanism for Hierarchical Wireless Sensor Networks. In IEEE Sarnoff Symposium (Sarnoff), pages 35–39, 2009.
	In order to protect the sensitive data and the sensor readings, secret keys should be used to encrypt the exchanged messages between communicating nodes. In this paper, we propose a new key pre-distribution scheme for hierarchical WSNs with proved peroperties that are particularly beneficial to the resource-constrained largescale WSNs.
[sguo-11:2008]	Long Zheng, Mianxiong Dong, Song Guo, Minyi Guo and LiLi. I-Cache Tag Reduction for Low Power Chip Multiprocessor. In IEEE International Symposium on Parallel and Distributed Processing with Applications, pages 196–202, 2009.
	Energy consumption is a major consideration in microprocessor optimization. This paper presents a tag-reduction based approach for energy saving in L1 I-Cache (instruction cache) of Chip Multiprocessors (CMP). To our best knowledge, this is the first work that extends the tag reduction technique to the CMP. We formulate our approach to 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. The experimental results show that our proposed algorithms can save the total power up to 45.33one that the tag-reduction is not used. They outperform significantly the tag-reduction based algorithm on single-core processor as well.
[sguo-12:2008]	Song Guo, Mianxiong Dong, and Minyi Guo. A Comparative Analysis of Mobility-based Lifetime-Aware Multicast Routing Protocols for MANETs. In International Conference on Mobile Computing and Ubiquitous Networking, 2008.
	We consider the performance issues of a group of lifetime-aware multicast routing protocols in mobile ad hoc networks that use omni-directional antennas and have limited energy resources. In order to verify if these protocols posses other advantages, e.g. in terms of communication overhead and packet delivery ratio, a well-known and conventional multicast routing protocol is also chosen to be compared against. The extensive simulation results have shown that the lifetime-aware multicast routing protocols, especially the one with localized lifetime-enhancement operation, not only significantly improve the multicast communication lifetime, but also achieve higher packet delivery ratio, and on the other hand they only occur minor extra communication overhead.
[sguo-14:2008]	Deze Zeng, Minyi Guo, Xin Liu, Song Guo, Hai Jin and Mianxiong Dong. An Accurate and Energy Efficient Fetch Direction Orientation Mechanism for Trace Cache. In Proceedings of the 2009 International Conference on Parallel Processing Workshops (International Symposium on Embedded Multicore Systems-on-Chip), pages 566–573 2009.
	Energy and performance efficiency of fetch unit is critical to processor design. Much research has focused on improving the energy efficiency of trace cache, such as dynamic direction prediction based trace cache (DPTC). A more efficient mechanism called advance direction directed trace cache (ADDTC) is proposed in this paper. By extending branch target buffer (BTB) with trace control information, whether trace cache hits or not can be predicted before access to trace cache. As a result, the fetch direction can be predicted that the simultaneous access can be avoided. We evaluated the energy consumption and performance of ADDTC. ADDTC achieves great energy saving with only little performance degradation.
[sguo-15:2008]	Deze Zeng, Minyi Guo, Song Guo, Mianxiong Dong, and Hai Jin. The Design and Evaluation of a Selective Way based Trace Cache. In Proceedings of the 8th International Conference on Advanced Parallel Processing Technologies, Lecture Notes In Computer Science; Vol. 5737, pages 95–109, 2009.
	Conventional trace cache (CTC) usually adopts set associate structure which requires probing all the data ways in parallel, but the output of only the matched way is used, the energy spent for accessing the other ways is wasted. To eliminate or reduce the wasted energy and make trace cache more energy efficient while maintaining high performance, in this paper, we propose an energy efficient trace cache, selective way based trace cache (SWTC), which probes only the selected way(s) instead of probing all the data ways. Simulation results show that it can save 40% energy on average and achieves almost the same performance compared to CTC.
[sguo-16:2008]	Xiaofei Liu, Song Guo, and A. El Saddik. Communication Complexity Evaluation for Longest-lived Directional Multicasting in WANETs. In IEEE International Conference on Communications (ICC), pages 3029–3033, May 2008.
	We consider the problem of maximizing the multicast lifetime in wireless ad hoc networks with directional antennas. We explore some important properties of this optimization problem from a graph theory perspective and derive several localized operations that are especially beneficial to the resource-constrained (e.g. limited energy, memory, and computation capabilities) wireless ad hoc networks. The localized operations have low complexity for both memory and computation requirements at each node. Our simulation results show that the proposed localized operations would allow our distributed algorithms to achieve an expected linear communication complexity.
[sguo-17:2008]	Song Guo, Minyi Guo, and Victor Leung. Exploring the Multicast Lifetime Capacity of WANETs with Directional Multibeam Antennas. In IEEE International Conference on Computer Communications (INFOCOM), 2009.
	We explore the multicast lifetime capacity of energy-limited wireless ad hoc networks using directional multibeam antennas by formulating and solving the corresponding optimization problem. In such networks, each node is equipped with a practical smart antenna array that can be configured to support multiple beams with adjustable orientation and beamwidth. The special case of this optimization problem in networks with single beams have been extensively studied and shown to be NP-hard. In this paper, we provide a globally optimal solution to this problem by developing a general MILP formulation that can apply to various configurable antenna models, many of which are not supported by the existing formulations. The multicast lifetime capacity is then quantitively studied by simulations. The experimental results show that using two-beam antennas can exploit most lifetime capacity of the networks for multicast communications.
[sguo-18:2008]	Xiaofei Liu, Song Guo, and Victor Leung. A Message Complexity Oriented Design of Distributed Algorithm for Long-lived Multicasting in Wireless Sensor Networks. In Proceedings of 17th IEEE International Conference on Computer Communications and Networks, pages 1–6, 2008.
	We consider an optimization problem in wireless sensor networks (WSNs) that is to find a multicast tree rooted at the source node and including all the destination nodes such that the lifetime of the tree is maximized. While a recently proposed distributed algorithm for this problem guarantees to obtain optimal solutions, we show that its high message complexity may prevent such contribution from being practically used in resource-constrained WSNs. In this paper, we proposed a new distributed suboptimal algorithm that achieves a good balance on the algorithmoptimality and message complexity. In particular, we prove that it has a linearmessage complexity. The tradeoff between algorithm sub-optimality and message complexity is also studied by simulations.
[sguo-19:2008]	Xiaofei Liu, Song Guo, Abdulmotaleb El-Saddik, and Victor Leung. A Unified Formulation of the Multicast Lifetime Optimization Problem in WANETs. In International Conference on Wireless Networks, pages 381– 386, 2008.
	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 configurable antenna models including highly and moderately directional antenna types.
[sguo-20:2008]	Chih-Hao Hsu, Song Guo, Rung-Chin Chen, and Shou-Kuo Dai. Using Domain Ontology to Implement a Frequently Asked Questions System. In World Congress on Computer Science and Information Engineering, pages 714–718, 2009.
	In recent years, the application of ontology has been already toward the diversification under the development of the semantic web technology. As the communicated bridge of the users and the machines, ontology should be upgraded while the information changes. Thus it is an important subject to expand ontology with the changing information. So we propose an automation on-line FAQ (Frequently Asked Questions) system that has the learning ability.We except that the system can reply answers and extend ontology.
[sguo-22:2008]	An-Ni Shen and Song Guo. Key Re-establishment Protocols in Hierarchical Wireless Sensor Networks. In European Wireless, pages 184–188, 2009.
	Traditional asymmetric key cryptosystems are infeasible in WSN due to its low capacity at each senor node. In this paper, we propose a new key distribution scheme for hierarchical WSNs with renewable network devices.
[sguo-23:2008]	Song Guo, Minyi Guo, and Victor Leung. A Linear Message Distributed Multicast Algorithm with Guaranteed Directional Communication Lifetime in WANETs. In IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), pages 92–101. 2008.
	We propose a new distributed multicast algorithm for the lifetime optimization problem in wireless ad hoc networks. Its performance, in terms of both approximation ratio and message complexity, is guaranteed by our theoretical analysis. The numerical experiments verify the correctness of our theoretical results.

Books

[minyi-11:2008]

Minyi Guo and Hai Jin. Frontier of Computer Science and Technology. IEEE Computer Society Press, USA, 2008.

Chapters in Book

[sguo-27:2008]

Song Guo and Victor Leung. Chapter 4: Performance Evaluation of Energy Efficient Multicast Algorithms for Providing Longest Lifetime in WANETs, Energy Efficiency Research, pages 87 – 112. Nova Science Publishers, 2009.

Grants

[sguo-28:2008]	Song Guo. JSPS Grant-in-Aid for Scientific Research, 2008 - 2010.
[sguo-29:2008]	Song Guo. Competitive Research Funding, 2008.

Academic Activities

[minyi-12:2008]	Minyi Guo, 2002–. Member, IEICE
[minyi-13:2008]	Minyi Guo, 2000–. Senior member, IEEE, IEEE Computer Society
[minyi-14:2008]	Minyi Guo, 2000–. Member, ACM
[minyi-15:2008]	Minyi Guo, 1995–. Member, IPSJ
[minyi-16:2008]	Minyi Guo, December 2008. Steering Committee Chair, The 2008 International Symposium on Parallel and Distributed Computing with Applications (ISPA2008).
[minyi-17:2008]	Minyi Guo, December 2008. Steering Committee Chair, the 2008 International Conference on Embedded and Ubiquitous Computing (EUC2008)
[sguo-30:2008]	Song Guo, 2001 -. Member, ACM, IEEE, IEEE ComSoc
[sguo-31:2008]	Song Guo, 2004 -. Technical Committee Member, IEEE Ad Hoc and Sensor Networks Technical Committee
[sguo-32:2008]	Song Guo, 2001 -. Member of Technical Program Committee: IEEE Conference on Computer and Information Science, 2008 & 2009 Conference on Communications and Networking in China, 2008 IEEE Wireless Communications and Networking Conference, 2008 IEEE Symposium on Personal, Indoor and Mobile Radio Communications, 2008 Workshop on Modelling and Design of Wireless Mesh Networks, 2008 IFIP Conference on Embedded and Ubiquitous Computing, 2008 IEEE/IFIP Symposium on Trust, Security and Privacy for Pervasive Applications, 2008 & 2009 Conference on Information Systems, Technology and Management, 2008 IEEE Conference on Embedded Software and Systems, 2009 IEEE Conference on Ubiquitous Intelligence and Computing, 2009 ACMWorkshop on Foundations ofWireless Ad Hoc and Sensor Networking and Computing, 2009 IEEE Workshop on Performance Analysis and Enhancement of Wireless Networks, 2009 International Conference on Ubiquitous Information Technologies & Applications, 2009 IEEE International Conference on Scalable Computing and Communications, 2009 IEEE International Conference on Computational Science and Engineering, 2009 ACIS Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 2009 International Workshop on Localized Algorithms and Protocols for Wireless Sensor Networks, 2009 IEEE International Workshop on Wireless Network Algorithm and Theory, 2009
[sguo-33:2008]	Song Guo, 2008. General Chair, International Workshop on Modeling, Analysis and Simulation of Sensor Networks
[sguo-34:2008]	Song Guo, 2009. Vice Program Co-Chair, International Conference on Frontier of Computer Science and Technology
[sguo-35:2008]	Song Guo, 2008. International Liaison Co-Chair, International Conference for Young Computer Scientists
[sguo-36:2008]	Song Guo, 2008. General Chair, International Workshop on Ubiquitous Wireless Mesh Networking
[sguo-37:2008]	Song Guo, 2006 -. Editorial Board Member, the Open Information Systems Journal
[sguo-38:2008]	Song Guo, 2008. Reviewing Activities for Archived Journals: IEEE Transactions on Computers IEEE Transactions on Mobile Computing IEEE Transactions on Parallel and Distributed Systems IEEE Transactions on Vehicular Technologies ACM Wireless Networks IEEE Communications Letters Information Processing Letters Elsevier Journal of Parallel and Distributed Computing
[sguo-39:2008]	Song Guo, 2009. Associate Editor, IEICE Transactions on Information and Systems

Ph.D, Master and Bachelor Theses

[minyi-18:2008]	Masato Honda. Graduation Thesis: Performance Evaluation of UMP Configuration Using Dynamic Processing Library, University of Aizu, 2008. Thesis Advisor: Minyi Guo.
[minyi-19:2008]	Keishi Fujita. Graduation Thesis: Development and Evaluation of Task Decomposition Function in UMP, University of Aizu, 2008. Thesis Advisor: Minyi Guo.
[minyi-20:2008]	Tomohiro Sugahara. Graduation Thesis: DL-PE: A Novel Execution Module to Load Library in Ubiquitous Multi-Processor, University of Aizu, 2008. Thesis Advisor: Minyi Guo.
[minyi-21:2008]	Takashi Suzuki. Graduation Thesis: Cache Enhancement for Task Decomposition Module in the UMP System and Its Evaluation for Practical Uses, University of Aizu, 2008. Thesis Advisor: Minyi Guo.
[sguo-40:2008]	Sakuma Tatsuya. Graduation Thesis: Development of Monitoring Application for USB Framework in UMP System, University of Aizu, 2008. Thesis Advisor: Song Guo
[sguo-41:2008]	Sekiguchi Riyuusuke. Graduation Thesis: Localization Algorithms for Wireless Sensor Networks, University of Aizu, 2008. Thesis Advisor: Song Guo
[sguo-42:2008]	Ootomo Yuuma. Graduation Thesis: Optimal Resource Allocation Algorithm, University of Aizu, 2008. Thesis Advisor: Song Guo

Others

[minyi-22:2008]	Minyi Guo. Editor in Chief, International Journal of Embedded Systems
[minyi-23:2008]	Minyi Guo. Editor, Journal of Embedded Computing
[minyi-24:2008]	Minyi Guo. Editor, International Journal of Web and Grid Services
[minyi-25:2008]	Minyi Guo. Editor, International Journal of High Performance Computing and Networking
[minyi-26:2008]	Minyi Guo. Editor, International Journal of Computer and Applications
[minyi-27:2008]	Minyi Guo. Editor, Journal of Pervasive Computing and Communications

2010 THE UNIVERSITY OF AIZU ALL RIGHTS RESERVED