Repacking on Demand for Hierarchical Cellular Networks

In mobile telecommunications operation, radio channels are scarce resources and should be carefully assigned. One possibility is to deploy the hierarchical cellular network (HCN). This paper studies a HCN channel assignment scheme called repacking on demand (RoD). RoD was originally proposed for wireless local loop networks. We expend this work to accommodate mobile HCN. A simulation model is proposed to study the performance of HCN with RoD and some previously proposed schemes. Our study quantitatively indicates that RoD may significantly outperform the previous proposed schemes. Hsien-Ming Tsai was born in Tainan, Taiwan, R.O.C., in 1973. He received the double B.S. degrees in Computer Science & Information Engineering (CSIE) and Communication Engineering, the M.S. degree in CSIE, and the Ph.D. degree in CSIE from National Chiao-Tung University (NCTU), Taiwan, in 1996, 1997, and 2002, respectively. He is currently a research specialist in Quanta Research Institute, Quanta Computer Inc. His research interests are in the areas of cellular protocols (UMTS/GPRS/GSM/DECT), cellular multimedia (MPEG-4 Audio/Speech), and embedded systems. He is an IEEE member. Ai-Chun Pang was born in Hsinchu, Taiwan, R.O.C., in 1973. She received the B.S., M.S. and Ph.D. degrees in Computer Science and Information Engineering from National Chiao Tung University (NCTU) in 1996, 1998 and 2002, respectively. She joined the Department of Computer Science and Information Engineering, National Taiwan University (NTU), Taipei, Taiwan, as an Assistant Professor in 2002. Her research interests include design and analysis of personal communications services network, mobile computing, voice over IP and performance modeling. Yung-Chun Lin was born in Kaohsiung, Taiwan, R.O.C., in 1978. He received the B.S. and M.S. degrees in Computer Science and Information Engineering (CSIE) from National Chiao-Tung University (NCTU), Taiwan, in 2001, 2003, respectively. He is currently pursuing the Ph.D. degree in CSIE. His research interests include design and analysis of a personal communications services network, the cellular protocols (UMTS/GPRS/GSM), and mobile computing. Yi-Bing Lin received his BSEE degree from National Cheng Kung University in 1983, and his Ph.D. degree in Computer Science from the University of Washington in 1990. From 1990 to 1995, he was with the Applied Research Area at Bell Communications Research (Bellcore), Morristown, NJ. In 1995, he was appointed as a professor of Department of Computer Science and Information Engineering (CSIE), National Chiao Tung University (NCTU). In 1996, he was appointed as Deputy Director of Microelectronics and Information Systems Research Center, NCTU. During 1997-1999, he was elected as Chairman of CSIE, NCTU. His current research interests include design and analysis of personal communications services network, mobile computing, distributed simulation, and performance modeling. Dr. Lin has published over 150 journal articles and more than 200 conference papers. Lin is an Adjunct Research Fellow of Academia Sinica, and is Chair Professor of Providence University. Lin serves as consultant of many telecommunications companies including FarEasTone and Chung Hwa Telecom. Lin is an IEEE Fellow and an ACM Fellow.     

Scheduling for time-division based shared channel allocation for UMTS

The Universal Mobile Telecommunications System (UMTS) adopts the WCDMA technology as the radio access interface to provide variable transmission rate services. There are four classes of connections identified in UMTS, which are the conversational, streaming, interactive, and background connections. To efficiently utilize radio bandwidth, the shared channel approach is proposed to deliver the packets for the interactive and background connections. This paper proposes a “Shared-Channel Assignment and Scheduling” (SCAS) algorithm to periodically allocate shared channels to serve interactive and background connections. We conduct formal mathematical proofs and simulation experiments to investigate the performance of the SCAS algorithm. We formally prove that with SCAS, a shared channel can be fully utilized (i.e., the utilization of a shared channel can be up to 100%) to serve the interactive connections. Our analysis indicates that compared with the previously proposed shared channel allocation and scheduling algorithms, there are less computation and communication overheads introduced in the SCAS algorithm. The results of the simulation experiments indicate that it is preferred to set up the Transmission Time Interval (TTI; that is, the unit of time interval for shared channel allocation) smaller to optimize the performance of the SCAS algorithm, including the shared channel utilization and the average waiting time of a connection before getting transmission service. A preliminary version [11] of this work has been accepted by IEEE Wireless Communications and Networking Conference 2004. This paper is an extension of the proposed algorithm, and simulation and analysis are conducted to investigate the performance of the proposed algorithm. Chai-Hien Gan was born in Malaysia in 1971. He received his BS degree in computer science from Tamkang University in 1994, Taipei County, Taiwan, and both his MS. and Ph.D. degrees in computer science and information engineering from National Taiwan University, Taipei, Taiwan, in 1996 and 2005, respectively. Since March 2005, he has been a Research Assistant Professor in Department of Computer Science, National Chiao Tung University, R.O.C. His current research interests include wireless mesh networks, mobile computing, personal communications services, and wireless Internet. Phone Lin received his BSCSIE degree and Ph.D. degree from National Chiao Tung University, Taiwan, R.O.C. in 1996 and 2001, respectively. From August 2001 to July 2004, he was an Assistant Professor in Department of CSIE and Graduate Institute of Graduate of Networking and Multimedia, National Taiwan University, R.O.C. Since August 2004, he has been an Associate Professor in Department of CSIE and Graduate Institute Graduate of Networking and Multimedia, National Taiwan University, R.O.C. His current research interests include personal communications services, wireless Internet, and performance modeling. Dr. Lin is an Associate Editor for IEEE Transactions on Vehicular Technology, Editor for IEEE Wireless Communications special issue on Mobility and Resource Management and a Guest Editor for ACM/Springer MONET special issue on Wireless Broad Access. He is also an Associate Editorial Member for the WCMC Journal. P. Lin’s email and website addresses are plin@csie.ntu.edu.tw and http://www.csie.ntu.edu.tw/~plin, respectively. Nei-Chiung Perng is presently a Ph.D. student in the Department of Computer Science and Information Engineering, National Taiwan University. He received his Bachelor and Master degrees in the Department of Computer and Information Science, National Chiao Tung University in 1999 and 2001, respectively. His research interests include real-time systems and scheduling algorithms. Tei-Wei Kuo received B.S.E. degree in computer science and information engineering from National Taiwan University in Taipei, Taiwan, in 1986. He received the M.S. and Ph.D. degrees in computer sciences from the University of Texas at Austin in 1990 and 1994, respectively. He is currently a Professor and the Chairman of the Department of Computer Science and Information Engineering of the National Taiwan University, Taiwan, ROC. He was an Associate Professor in the Department of Computer Science and Information Engineering of the National Chung Cheng University, Taiwan, ROC, from August 1994 to July 2000. Dr. Kuo is a senior member of the IEEE computer society. His research interest includes embedded systems, real-time process scheduling, real-time operating systems, and real-time databases. He has over 100 technical papers published or been accepted in international journals and conferences and has a book “Real-Time Database Systems: Architecture and Techniques” published by Kluwer Academic Publishers (ISBN 0-7923-7218-2, USA). He is the Program Co-Chair of IEEE 7th Real-Time Technology and Applications Symposium, 2001, and an associate editor of the Journal of Real-Time Systems since 1998. He is an executive committee member of the IEEE Technical Committee on Real-Time Systems in 2005 and the steering committee chair of IEEE RTCSA’05. Dr. Kuo has consulted for government and industry on problems in various real-time and embedded systems designs. Dr. Kuo received several research awards in Taiwan, including the Distinguished Research Award from the ROC National Science Council in 2003 and the Young Scholar Research Award from Academia Sinica, Taiwan, ROC, in 2001. Ching-Chi Hsu was born in Taipei, Taiwan in 1949. He received his BS degree in physics from National Tsing Hwa. University in 1971, Hsishu, Taiwan, and both his MS. and Ph.D. degrees in computer engineering from EE department of National Taiwan University, Taipei, Taiwan, in 1975 and 1982, respectively. In 1977, he joined the faculty of the Department of Computer Science and Information Engineering at National Taiwan University and became an associate professor in 1982. During the years between 1987 and 2002, he was first engaged as a professor and became the chairman of the department. During his tenure in National Taiwan University, Dr. Hsu was a visiting scholar of Computer Science Department, Stanford University from 1984 to 1985. After serving in National Taiwan University for over 25 years, Dr. Hsu had left and was promoted as the president of Kai Nan University in 2002. Starting from February 2004, Dr. Hsu has been the executive vice president of the Institute for Information Industry in which he is mainly in charge of accelerating the growth of information industry in the whole nation. His research interests include distributed processing of data and knowledge, mobile computing and wireless networks.     

A Relay-Based MAC Protocol for Multi-Rate and Multi-Range Infrastructure Wireless LANs

Auto rate adaptation mechanisms have been proposed to improve the throughput in wireless local area networks with IEEE 802.11a/b/g standards that can support multiple data rate at the physical layer. However, even with the capability of transmitting multi-packets with multi-rate IEEE 802.11 PHY, a mobile host near the fringe of the Access-Point's (AP's) transmission range still needs to adopt a low-level modulation to cope with the lower signal-to-noise ratio (SNR), Thus, it can not obtain a data rate as high as that of a host near AP in most cases. According to the characteristics of modulation schemes, the highest data rate between a pair of mobile hosts will be inversely proportional with the transmission distance. Considering these factors, we here demonstrate a Relay-Based Adaptive Auto Rate (RAAR) protocol that can find a suitable relay node for data transmission between transmitter and receiver, and can dynamically adjust its modulation scheme to achieve the maximal throughput of a node according to the transmission distance and the channel condition. The basic concept is that the best modulation schemes are adaptively used by a wireless station to transmit an uplink data frame, according to the path loss condition between the station itself and a relay node, and that between the relay node and AP, thus delivering data at a higher overall data rate. Evaluation results show that this scheme provides significant throughput improvement for nodes located at the fringe of the AP's transmission range, thus remarkably improving overall system performance. Jain-Shing Liu was born in Taipei, Taiwan, in 1970. He received the Ph.D. degree in Department of Computer and Information Science, National Chiao Tung University, Hsinchu, Taiwan. He is currently with the faculty of the Department of Computer Science and Information Management, Providence University, Taichung, Taiwan 433, ROC. His research interests include wireless communication protocol design, performance analysis and modeling, personal communication networks, and distributed simulation. Dr. Liu is a member of IEEE and IEICE. Chunhung Richard Lin was born in Kaohsiung, Taiwan. He received the B.S. and M.S. degrees from the Department of Computer Science and Information Engineering, National Taiwan University, in 1987 and 1989, respectively, and the Ph.D. degree from Computer Science Department, University of California, Los Angeles (UCLA), in 1996. Dr. Lin joined National Chung Cheng University in Taiwan in 1996. Since August 2000, he has been with the Department of Computer Science and Engineering, National Sun Yat-Sen University, Kaohsiung, Taiwan. His research interests include the design and control of personal communication networks, protocol design and implementation for differentiated/integrated services in mobile wireless networks, mobile Internet, distributed simulation, and embedded operating system design and implementation. His email address is: lin@cse.nsysu.edu.tw. Dr. Lin is an ACM member. He received the 2001 Junior Professor Research Award from National Sun Yat-Sen University and the 2000 Investigative Research Award from the Pan Wen Yuan Foundation, Taiwan, ROC.     

High Performance Wireless Switch Protocol for IEEE 802.11 Wireless Networks

All mobile stations (STAs) in IEEE 802.11 infrastructure wireless local area networks (IWLAN) are coordinated by an access point (AP). Within the 2.4 GHz unlicensed industry, science, and medicine (ISM) band defined in the IEEE 802.11 2.4 GHz physical layer (PHY) specifications, three channels are available for concurrently transferring data packets at the coverage area of an AP. In most of small/medium enterprises or home environments, an AP with one selected channel is sufficient for covering whole service area, but this implies that the radio resources for the remaining two channels are wasted. In order to overcome the drawback, we propose a new and simple media access control (MAC) protocol, named wireless switch protocol (WSP), for increasing the throughput of IEEE 802.11 IWLAN network to support high quality multimedia traffic. This is achieved by allowing any pair of STAs in IWLAN to exchange data packets in one of other idle channels after their handshake with each other in the common channel controlled by AP. Simulation results show that the total network throughput of WSP depends on the time taken by channel switching, and on the ‘Intranet’ and ‘Internet’ traffic distribution, where the Intranet and Internet mean data transmission between STAs in IWLAN and between the STA and wired host, respectively. When all data packets are Intranet traffic and the traffic load is heavy, the ratio of Goodput for the proposed WSP to that of IEEE 802.11 standard approximates 400%. In the worse case of all Internet traffic, the proposed WSP still obtains the similar throughput as that of IEEE 802.11 standard.Jenhui Chen was born on October 12, 1971 in Taipei, Taiwan, Republic of China. He received the Bachelor’s and Ph.D. degree in Computer Science and Information Engineering (CSIE) from Tamkang University in 1998 and 2003, respectively. In the Spring of 2003, he joined the faculty of Computer Science and Information Engineering Department at Chang Gung University and served as the Assistant Professor. He occupies the supervisor of Network Department in the Information Center, Chang Gung University. Dr. Chen once served the reviewer of IEEE Transactions on Wireless Communications, ACM/Kluwer Mobile Networks and Applications (MONET), and Journal of Information Science and Engineering. His main research interests include design, analysis, and implementation of communication and network protocols, wireless networks, milibots, and artificial intelligence. He is a member of ACM and IEEE.Ai-Chun Pang was born in Hsinchu, Taiwan, R.O.C., in 1973. She received the B.S., M.S. and Ph.D. degrees in Computer Science and Information Engineering from National Chiao Tung University (NCTU) in 1996, 1998 and 2002, respectively. She joined the Department of Computer Science and Information Engineering, National Taiwan University (NTU), Taipei, Taiwan, as an Assistant Professor in 2002. Her research interests include design and analysis of personal communications services network, mobile computing, voice over IP, and performance modeling.Shiann-Tsong Sheu received his B.S. degree in Applied Mathematics from National Chung Hsing University in 1990, and obtained his Ph.D. degree in Computer Science from National Tsing Hua University in May of 1995. From 1995 to 2002, he was an Associate Professor at the Department of Electrical Engineering, Tamkang University. Since Feb. 2002, he has become a Professor at the Department of Electrical Engineering, Tamkang University. Dr. Sheu received the outstanding young researcher award by the IEEE Communication Society Asia Pacific Board in 2002. His research interests include next-generation wireless communication, WDM networks and intelligent control algorithms.Hsueh-Wen Tseng received his B.S. degree in electrical engineering from Tamkang University, Taipei country, Taiwan, in 2001 and M.S. degree in electrical engineering from National Taiwan University of Science and Technology, Taipei, Taiwan, in 2003. He is currently pursuing the Ph. D. degree at the Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan. His research interests include design, analysis and implementation of network protocols and wireless communications.     

HISNs: Distributed gateways for application-level integration of heterogeneous wireless networks

Integration of different kinds of wireless networks to provide people seamless and continuous network access services is a major issue in the B3G network. In this paper, we propose and implement a novel Heterogeneous network Integration Support Node design (HISN) and a distributed HISN network architecture for the integration of heterogeneous networks, under which the Session Mobility, Personal Mobility, and Terminal Mobility for mobile users can be maintained through the Session Management mechanism. Thus, the HISN node can serve as an agent for the user to access Internet services independent of underlying communication infrastructure. Our design is transparent to the bearer networks and the deployment of the HISN network does not need to involve the operators of the heterogeneous wireless networks. This paper is an extension of the work that won the championship of the Mobile Hero contest sponsored by Industrial Development Bureau of Ministry of Economic Affairs, Taiwan, R.O.C., and was awarded USD 30,000. The work of Lin, Chang and Cheng was supported in part by the National Science Council (NSC), R.O.C, under the contract number NSC94-2213-E-002-083 and NSC94-2213-E-002-090, and NSC 94-2627-E-002-001, Ministry of Economic Affairs (MOEA), R.O.C., under contract number 93-EC-17-A-05-S1-0017, the Computer and Communications Researches Labs/Industrial Technology Research Institute (CCL/ITRL), Chunghwa Telecom Labs, Telcordia Applied Research Center, Taiwan Network Information Center (TWNIC), and Microsoft Corporation, Taiwan. The work of Fang was supported in part by the US National Science Foundation Faculty Early Career Development Award under grant ANI-0093241 and US National Science Foundation under grant DBI-0529012. Phone Lin (M’02-SM’06) received his BSCSIE degree and Ph.D. degree from National Chiao Tung University, Taiwan, R.O.C. in 1996 and 2001, respectively. From August 2001 to July 2004, he was an Assistant Professor in Department of Computer Science and Information Engineering (CSIE), National Taiwan University, R.O.C. Since August 2004, he has been an Associate Professor in Department of CSIE and Graduate Institute of Networking and Multimedia, National Taiwan University, R.O.C. His current research interests include personal communications services, wireless Internet, and performance modeling. Dr. Lin is an Associate Editor for IEEE Transactions on Vehicular Technology, a Guest Editor for IEEE Wireless Communications special issue on Mobility and Resource Management, and a Guest Editor for ACM/Springer MONET special issue on Wireless Broad Access. He is also an Associate Editorial Member for the WCMC Journal. P. Lin’s email and website addresses are plin@csie.ntu.edu.tw and http://www.csie.ntu.edu.tw/∼plin, respectively. Huan-Ming Chang received the BSCSIE degree and Master CSIE degree from National Taiwan University, R.O.C. in 2003 and 2005, respectively. His current research interest includes wireless Internet. H.-M. Chang’s email address is r91114@csie.ntu.edu.tw. Yuguang Fang received a Ph.D. degree in Systems and Control Engineering from Case Western Reserve University in January 1994, and a Ph.D. degree in Electrical Engineering from Boston University in May 1997. From June 1997 to July 1998, he was a Visiting Assistant Professor in Department of Electrical Engineering at the University of Texas at Dallas. From July 1998 to May 2000, he was an Assistant Professor in the Department of Electrical and Computer Engineering at New Jersey Institute of Technology. In May 2000, he joined the Department of Electrical and Computer Engineering at University of Florida where he got the early promotion to Associate Professor with tenure in August 2003 and to Full Professor in August 2005. He has published over 180 papers in refereed professional journals and conferences. He received the National Science Foundation Faculty Early Career Award in 2001 and the Office of Naval Research Young Investigator Award in 2002. He is currently serving as an Editor for many journals including IEEE Transactions on Communications, IEEE Transactions on Wireless Communications, IEEE Transactions on Mobile Computing, and ACM Wireless Networks. He is also actively participating in conference organization such as the Program Vice-Chair for IEEE INFOCOM’2005, Program Co-Chair for the Global Internet and Next Generation Networks Symposium in IEEE Globecom’2004 and the Program Vice Chair for 2000 IEEE Wireless Communications and Networking Conference (WCNC’2000). Shin-Ming Cheng received the BSCSIE degree in 2000 from National Taiwan University, Taiwan, R.O.C., where he is currently working toward the Ph.D. degree in the Department of Computer Science and Information Engineering, National Taiwan University. His current research interests include mobile computing, personal communications services, and wireless Internet. S.-M. Cheng’s email and website addresses are shimi@pcs.csie.ntu.edu.tw and http://www.pcs.csie.ntu.edu.tw/∼shimi, respectively.     

Scheduling Sleeping Nodes in High Density Cluster-based Sensor Networks

In order to conserve battery power in very dense sensor networks, some sensor nodes may be put into the sleep state while other sensor nodes remain active for the sensing and communication tasks. In this paper, we study the node sleep scheduling problem in the context of clustered sensor networks. We propose and analyze the Linear Distance-based Scheduling (LDS) technique for sleeping in each cluster. The LDS scheme selects a sensor node to sleep with higher probability when it is farther away from the cluster head. We analyze the energy consumption, the sensing coverage property, and the network lifetime of the proposed LDS scheme. The performance of the LDS scheme is compared with that of the conventional Randomized Scheduling (RS) scheme. It is shown that the LDS scheme yields more energy savings while maintaining a similar sensing coverage as the RS scheme for sensor clusters. Therefore, the LDS scheme results in a longer network lifetime than the RS scheme. Jing Deng received the B.E. and M.E. degrees in Electronic Engineering from Tsinghua University, Beijing, P. R. China, in 1994 and 1997, respectively, and the Ph.D. degree in Electrical and Computer Engineering from Cornell University, Ithaca, NY, in 2002. Dr. Deng is an assistant professor in the Department of Computer Science at the University of New Orleans. From 2002 to 2004, he visited the CASE center and the Department of Electrical Engineering and Computer Science at Syracuse University, Syracuse, NY as a research assistant professor, supported by the Syracuse University Prototypical Research in Information Assurance (SUPRIA) program. He was a teaching assistant from 1998 to 1999 and a research assistant from 1999 to 2002 in the School of Electrical and Computer Engineering at Cornell University. His interests include mobile ad hoc networks, wireless sensor networks, wireless network security, energy efficient wireless networks, and information assurance. Wendi B. Heinzelman is an assistant professor in the Department of Electrical and Computer Engineering at the University of Rochester. She received a B.S. degree in Electrical Engineering from Cornell University in 1995 and M.S. and Ph.D. degrees in Electrical Engineering and Computer Science from MIT in 1997 and 2000 respectively. Her current research interests lie in the areas of wireless communications and networking, mobile computing, and multimedia communication. Dr. Heinzelman received the NSF Career award in 2005 for her work on cross-layer optimizations for wireless sensor networks, and she received the ONR Young Investigator award in 2005 for her research on balancing resource utilization in wireless sensor networks. Dr. Heinzelman was co-chair of the 1st Workshop on Broadband Advanced Sensor Networks (BaseNets '04), and she is a member of Sigma Xi, the IEEE, and the ACM. Yunghsiang S. Han was born in Taipei, Taiwan, on April 24, 1962. He received the B.S. and M.S. degrees in electrical engineering from the National Tsing Hua University, Hsinchu, Taiwan, in 1984 and 1986, respectively, and the Ph.D. degree from the School of Computer and Information Science, Syracuse University, Syracuse, NY, in 1993. From 1986 to 1988 he was a lecturer at Ming-Hsin Engineering College, Hsinchu, Taiwan. He was a teaching assistant from 1989 to 1992 and from 1992 to 1993 a research associate in the School of Computer and Information Science, Syracuse University. From 1993 to 1997 he was an Associate Professor in the Department of Electronic Engineering at Hua Fan College of Humanities and Technology, Taipei Hsien, Taiwan. From 1997 to 2004 he was with the Department of Computer Science and Information Engineering at National Chi Nan University, Nantou, Taiwan. He was promoted to Full Professor in 1998. From June to October 2001 he was a visiting scholar in the Department of Electrical Engineering at University of Hawaii at Manoa, HI, and from September 2002 to January 2004 he was the SUPRIA visiting research scholar in the Department of Electrical Engineering and Computer Science and CASE center at Syracuse University, NY. He is now with the Graduate Institute of Communication Engineering at National Taipei University, Taipei, Taiwan. His research interests are in wireless networks, security, and error-control coding. Dr. Han is a winner of 1994 Syracuse University Doctoral Prize. Pramod K. Varshney was born in Allahabad, India on July 1, 1952. He received the B.S. degree in electrical engineering and computer science (with highest honors), and the M.S. and Ph.D. degrees in electrical engineering from the University of Illinois at Urbana-Champaign in 1972, 1974, and 1976 respectively. Since 1976 he has been with Syracuse University, Syracuse, NY where he is currently a Professor of Electrical Engineering and Computer Science and the Research Director of the New York State Center for Advanced Technology in Computer Applications and Software Engineering. His current research interests are in distributed sensor networks and data fusion, detection and estimation theory, wireless communications, intelligent systems, signal and image processing, and remote sensing he has published extensively. He is the author of Distributed Detection and Data Fusion, published by Springer-Verlag in 1997 and has co-edited two other books. Dr. Varshney is a member of Tau Beta Pi and is the recipient of the 1981 ASEE Dow Outstanding Young Faculty Award. He was elected to the grade of Fellow of the IEEE in 1997 for his contributions in the area of distributed detection and data fusion. In 2000, he received the Third Millennium Medal from the IEEE and Chancellor's Citation for exceptional academic achievement at Syracuse University. He serves as a distinguished lecturer for the AES society of the IEEE. He is on the editorial board Information Fusion. He was the President of International Society of Information Fusion during 2001.     

VE-mobicast: a variant-egg-based mobicast routing protocol for sensornets

In this paper, we present a new “spatiotemporal multicast”, called a “mobicast”, protocol for supporting applications which require spatiotemporal coordination in sensornets. The spatiotemporal character of a mobicast is to forward a mobicast message to all sensor nodes that will be present at time t in some geographic zone (called the forwarding zone) Z, where both the location and shape of the forwarding zone are a function of time over some interval (t _start ,t _end ). The mobicast is constructed of a series of forwarding zones over different intervals (t _start ,t _end ), and only sensor nodes located in the forwarding zone in the time interval (t _start ,t _end ) should be awake in order to save power and extend the network lifetime. Existing protocols for a spatiotemporal variant of a multicast system were designed to support a forwarding zone that moves at a constant velocity, , in sensornets. To consider the path of a mobile entity which includes turns, this work mainly develops a new mobicast routing protocol, called the variant-egg-based mobicast (VE-mobicast) routing protocol, by utilizing the adaptive variant-egg shape of the forwarding zone to achieve high predictive accuracy. To illustrate the performance achievement, a mathematical analysis is conducted and simulation results are examined. Yuh-Shyan Chen received the M.S. and Ph.D. degrees in Computer Science and Information Engineering from the National Central University, Taiwan, Republic of China, in June 1991 and Jan. 1996, respectively. He joined the faculty of Department of CSIE, Chung-Hua University, Taiwan, in 1996. He joined the Department of Statistic, National Taipei University in Aug. 2000, and joined the Department of CSIE, National Chung Cheng University in Aug. 2002. Dr. Chen is an associate Professor from Aug. 2003. Since 2006, he has been a Professor at the Department of CSIE, National Taipei University, Taiwan. Dr. Chen served as Co-Editors-in-Chief of International Journal of Ad Hoc and Ubiquitous Computing (IJAHUC); Editorial Board Member of Telecommunication System; Guest Editor of Telecommunication Systems, special issue on “Wireless Sensor Networks” (2004). He was a Vice Co-Chair, Wireless IP Symposium of WirelressCOM, USA (2005); Workshop Co-Chair, IEEE AHUC06, Taiwan (2006); Program Co-Chairs, IFIP NCUS06, Korea (2006). Dr. Chen also served as Program Committee Member of ICPP’03, ICDCS’04, ICCCN’01–06, MSN’05, CCN’02–06, CSA’04 06, NCS’06, MSEAT’03–06, WASN06, USN06, MHNET06, PESYS06, ML06, IWWN06, UIC06, ICWMC06, and HWN-RMQ06; IASTED Technical Committee on Telecommunications (2002–2005); WSEAS International Scientific Committee Member (from 2004). His paper wins the 2001 IEEE 15th ICOIN-15 Best Paper Award. Dr. Chen was a recipient of the 2005 Young Scholar Research Award given by National Chung Cheng University to four young faculty members, 2005. His recent research topics include mobile ad-hoc network, wireless sensor network, and 4G system. Dr. Chen is a member of the IEEE Computer Society and Phi Tau Phi Society. Shin-Yi Ann received the B.S. degree in computer science and engineering from the National Taiwan Ocean University, Taiwan, Republic of China, in June 2002 and the M.S. degree in computer science and information engineering from National Chung Cheng University, Taiwan, Republic of China, in July 2004. His research interest includes wireless sensor network. Yun-Wei Lin received the B.S. degree in computer and information science from the Aletheia University, Taiwan, Republic of China, in June 2003 and the M.S. degree in computer science and information engineering from National Chung Cheng University, Taiwan, Republic of China, in July 2005. His research interests include mobile ad hoc network and wireless sensor network.     

Feedback Closed-Loop Scheduling Discipline for QoS Guarantee in Mobile Applications

Multi-functional and high-quality services are indispensable for providing responsive information services in a highly interactive e-learning system. This work presents a problem-solving mechanism using closed-loop scheduling discipline to achieve QoS e-learning applications. In the closed-loop schedule, the feedback mechanism supports wireless mobile communications services with dynamic QoS requirements. This work presents a closed-loop architecture by cascading the open-loop schedule, the QoS probe, the Proportional-Integral-Derivative (PID) controller and the feedback mechanism. In this architecture, the relationship between input and output is defined using a Lagrange λ-calculus module. The module estimates the future QoS according to the current scheduling, while the controller parameters are tuned according to the system status to achieve dynamic scheduling. Simulation results with e-learning activities demonstrate that the closed-loop schedule outperforms existing disciplines in terms of service delay and system utilization. Jiann-Liang Chen was born in Taiwan on December 15, 1963. He received the Ph.D. degree in Electrical Engineering from National Taiwan University, Taipei, Taiwan in 1989. Since August 1997, he has been with the Department of Computer Science and Information Engineering of National Dong Hwa University, where he is a professor now. His current research interests are directed at Wireless Sensor Networks, Cellular Mobility Management and Personal Communication Systems. Nong-Kun Chen received MS degree in Computer Science and Information Engineering, from the National Dong Hwa University, Hualien, Taiwan, in 2000. He is currently a doctoral student in the Department of Computer Science and Information Engineering at the National Dong Hwa University. His main research focuses on the areas of mobile cellular networks and feedback control.     

A Development Environment for OSA-Based Applications over the Interworked WLAN and Cellular Networks

In this paper, we propose an OSA-based development environment for interworking WLAN and 3G cellular networks. The main goal of our work is to establish and create an environment that can serve as a demonstration of a working network for OSA-based application developers while featuring mobile services over the interworked LAN and 3G cellular networks. The proposed simulating environment has (i) a location update scheme that is used to obtain mobile users' locations and status information over the interworked WLAN and cellular networks, (ii) an instant message gateway (IMG) simulator that is developed to send and receive generic messages over the interworked WLAN and cellular networks, and (iii) a mapping of Parlay APIs onto SIP signaling messages for multiparty call applications over the interworked WLAN and cellular networks. An illustrated OSA-based application that utilizes the corresponding system functions and modules is developed and verified using the proposed simulating environment. Chung-Ming Huang received the B.S. degree in Electrical Engineering from National Taiwan University on 1984/6, and the M.S. and Ph.D. degrees in Computer and Information Science from The Ohio State University on 1987/12 and 1991/6 respectively. He is currently a professor in Department of Computer Science and Information Engineering, National Cheng Kung University, Taiwan, R.O.C. He is the director of The Promotion Center for Network Applications and Services, Innovative Communication Education Project, Ministry of Education, Taiwan, R.O.C. His research interests include broadband Internet and applications, wireless and mobile network protocols, ubiquitous computing and communications, and multimedia streaming. Tz-Heng Hsu received the B.S. degree from Department of Computer Science and Information Engineering, Feng Chia University on 1996/6, and the M.S. degree and Ph.D from Department of Computer Science and Information Engineering, National Cheng Kung University on 1998/7 and 2005/7, Taiwan, R.O.C. He is currently a assistant professor in Department of Computer Science and Information Engineering, Southern Taiwan University of Technology. His research interests are wireless and mobile network protocols, applications over interworked WLAN and cellular networks and communications, and multimedia streaming. Chih-Wen Chao received the B.S. degree from Department of Engineering Science, National Cheng Kung University on 2003/6, and the M.S. degree from Department of Computer Science and Information Engineering, National Cheng Kung University on 2005/7, Taiwan, R.O.C. His research interests are OSA-based applications and distributed multimedia systems.     

A Credit-Based On-Demand QoS Routing Protocol Over Bluetooth WPANs

The quality-of-service (QoS) communication that supports mobile applications to guarantee bandwidth utilization is an important issue for Bluetooth wireless personal area networks (WPANs). In this paper, we address the problem of on-demand QoS routing with interpiconet scheduling in Bluetooth WPANs. A credit-based QoS (CQ) routing protocol is developed which considers different Bluetooth packet types, because different types of Bluetooth packets have different bandwidth utilization levels. This work improves the bandwidth utilization of Bluetooth scatternets by providing a new interpiconet scheduling scheme. This paper mainly proposes a centralized algorithm to improve the bandwidth utilization for the on-demand QoS routing protocol. The centralized algorithm incurs the scalability problem. To alleviate the scalability problem, a distributed algorithm is also investigated in this work. The performance analysis illustrates that our credit-based QoS routing protocol achieves enhanced performance compared to existing QoS routing protocols.This work was supported by the National Science Council of the Republic of China under grant nos. NSC-92-2213-E-194-022 and NSC-93-2213-E-194-028. Yuh-Shyan Chen received the B.S. degree in computer science from Tamkang University, Taiwan, Republic of China, in June 1988 and the M.S. and Ph.D. degrees in Computer Science and Information Engineering from the National Central University, Taiwan, Republic of China, in June 1991 and January 1996, respectively. He joined the faculty of Department of Computer Science and Information Engineering at Chung-Hua University, Taiwan, Republic of China, as an associate professor in February 1996. He joined the Department of Statistic, National Taipei University in August 2000, and joined the Department of Computer Science and Information Engineering, National Chung Cheng University in August 2002. Dr. Chen served as Co-Editors-in-Chief of International Journal of Ad Hoc and Ubiquitous Computing (IJAHUC), Editorial Board Member of Telecommunication System Journal, International Journal of Internet Protocol Technology (IJIPT) and The Journal of Information, Technology and Society (JITAS). He also served as Guest Editor of Telecommunication Systems, special issue on “Wireless Sensor Networks” (2004), and Guest Editor of Journal of Internet Technology, special issue on “Wireless Internet Applications and Systems” (2002) and special issue on “Wireless Ad Hoc Network and Sensor Networks” (2004). He was a Vice Co-Chair, Wireless IP Symposium of WirelressCOM2005, USA (2005) and a Workshop Co-Chair of the 2001 Mobile Computing Workshop, Taiwan. Dr. Chen also served as IASTED Technical Committee on Telecommunications for 2002–2005, WSEAS International Scientific Committee Member (from 2004), Program Committee Member of IEEE ICPP'2003, IEEE ICDCS'2004, IEEE ICPADS'2001, ICCCN'2001–2005, MSN'2005, IASTED CCN'2002–2005, IASTED CSA'2004–2005, IASTED NCS'2005, and MSEAT'2003–2005. His paper wins the 2001 IEEE 15th ICOIN-15 Best Paper Award. Dr. Chen was a recipient of the 2005 Young Scholar Research Award given by National Chung Cheng University to four young faculty members, 2005. His recent research topics include mobile ad-hoc network, wireless sensor network, mobile learning system, and 4G system. Dr. Chen is a member of the IEEE Computer Society, IEICE Society, and Phi Tau Phi Society. Keng-Shau Liu received the M.S. degree in Computer Science and Information Engineering from National Chung Cheng University, Taiwan, Republic of China, in July 2004. His research includes wireless LAN, Bluetooth, and mobile learning.     

Private Authentication Techniques for the Global Mobility Network

Numerous authentication approaches have been proposed recently for the global mobility network (GLOMONET), which provides mobile users with global roaming services. In these authentication schemes, the home network operators can easily obtain the authentication key and wiretap the confidentiality between the roaming user and the visited network. This investigation provides a solution of authentication techniques for GLOMONET in order to prevent this weakness from happening and presents a secure authentication protocol for roaming services. In addition, a round-efficient version of the same authentication protocol is presented. Comparing with other related approaches, the proposed authentication protocol involves fewer messages and rounds in communication. Tian-Fu Lee was born in Tainan, Taiwan, ROC, in 1969. He received his B.S. degree in Applied Mathematics from National Chung Hsing University, Taiwan, in 1992, and his M.S. degree in Computer Science and Information Engineering from National Chung Cheng University, Taiwan, in 1998. He works as a lecturer in Leader University and pursues his Ph.D. degree at Department of Computer Science and Information Engineering, National Cheng Kung University, Taiwan. His research interests include cryptography and network security. Chi-Chao Chang received the BS degree in Microbiology from Soochow University in 1990 and the MS degree in Computer Science from State University of New York at Albany in 1992. He is currently working as an instructor in Chang Jung Christian University and a graduate student in National Cheng Kung University. His research interests are information security, mobile agent systems, anonymous digital signatures and quantum cryptography. Tzonelih Hwang was born in Tainan, Taiwan, in March 1958. He received his undergraduate degree from National Cheng Kung University, Tainan, Taiwan, in 1980, and the M.S. and Ph.D. degrees in Computer Science from the University of Southwestern Louisiana, USA, in 1988. He is presently a professor in Department of Computer Science and Information Engineering, National Cheng Kung University. His research interests include cryptology, network security, and coding theory.     

An Improved GGSN Failure Restoration Mechanism for UMTS

Universal mobile telecommunications system (UMTS) provides packet-switched data services for mobile users. To efficiently deliver packets in the UMTS core network, the PDP contexts (i.e., the routing information) are maintained in the volatile storage (e.g., memory) of SGSN, GGSN, and UE. The GGSN routes packets between the UMTS core network and external data networks, and thus has heavy traffic and computation loading, which may result in PDP contexts lost or corrupted, and the QoS of the UMTS network may degrade significantly. To resolve this issue, 3GPP 23.007 proposes a mechanism for GGSN failure restoration. In this mechanism, the corrupted PDP contexts can be restored through the PDP Context Activation procedure. However, this incurs extra signaling cost to the network. To reduce the network signaling cost and delay for restoration of the corrupted PDP contexts, this paper proposes an improved mechanism “GGSN Failure Restoration” (GFR) with different backup algorithms. The analytic models and simulation experiments are conducted to evaluate GFR.Our study indicates that the GFR mechanism can significantly reduce the cost for the PDP context restoration. Phone Lin (M'02) received his BSCSIE degree and Ph.D. degree from National Chiao Tung University, Taiwan, R.O.C. in 1996 and 2001, respectively. From August 2001 to July 2004, he was an Assistant Professor in Department of Computer Science and Information Engineering (CSIE), National Taiwan University, R.O.C. Since August 2004, he has been an Associate Professor in Department of Computer Science and Information Engineering (CSIE), National Taiwan University, R.O.C. His current research interests include personal communications services, wireless Internet, and performance modeling. Dr. Lin is a Guest Editor for IEEE Wireless Communications special issue on Mobility and Resource Management. He is also an Associate Editorial Member for the WCMC Journal. Guan-Hua Tu received his B.S.C.S.I.E degree from National Central University, Taiwan, R.O.C., in 2001 and his Master degree in Computer Science from National Taiwan University, Taiwan, R.O.C., in 2003. He is currently a software engineer in MediaTek Inc. His resarch interests include personal communication services, mobile computing, and performance modeling.     

A new pipelined analog-to-digital converter using current conveyors

A new pipelined analog-to-digital converter (ADC) using second-generation current conveyor (CCII) is presented. Two main building blocks of the pipelined ADC, sample-and-hold (S/H) circuit and multiplying digital-to-analog converter (MDAC) are constructed of CCII instead of operational amplifier (OA). Experimental results show that the proposed CCII-based pipelined ADC can work at 12.5 MHz with a 7.3-bit resolution. The DNL is within −0.4 LSB and 0.4 LSB and INL is within −0.8 LSB and 0.8 LSB, respectively. The pipelined ADC is realized in TSMC 0.35 μm CMOS technology and consumes 29 mW under a 3.3 V power supply. The core size is 0.85×0.85 mm². Sing-Yen Wu received the M.S. degree in the Department of Electronic Engineering from National Taipei University of Technology, Taipei, Taiwan, in 2005. His current research interests include CMOS pipelined analog-to-digital converters and mixed-signal integrated circuit. Lu-Po Liao received the M.S. degree in the Department of Electronic Engineering from National Taipei University of Technology, Taipei, Taiwan, in 2003. His current research interests include analog integrated circuit design and mixed-signal integrated circuit design. Chia-Chun Tsai received the Ph.D. degrees in Electrical Engineering from National Taiwan University, Taipei, Taiwan, 1991. From 1989 to 2005, he served at the Department of Electronic Engineering, National Taipei University of Technology, Taipei, Taiwan. Since 2005 he has been with the Department of Computer Science and Information Engineering, Nanhua University, Chiayi, Taiwan, where he is a Full Professor. His current research interests include VLSI design automation and mixed-signal IC designs.     

A novel encoding scheme and data delivery in ubiquitous computing systems

Accessing information through wireless devices is becoming more and more popular. When the size of the accessed information is large, a great amount of access latency is incurred while a mobile user (MU) migrates across cells. This paper investigates this problem and proposes an effective way of delivering such data to the MU in ubiquitous computing systems. A cell-encoding scheme is proposed for the support of this efficient data delivery. The method is carefully evaluated on its feasibility and efficiency. Chao-Chun Chen received his Ph.D. degree in the Department of Computer Science and Information Engineering at the National Cheng-Kung University, Taiwan, in 2004. Currently, he is an assistant professor of the Department of Information Management, Shih-Chien University Kaohsung Campus, Taiwan. His research interests include mobile/wireless data management, sensor networks, spatio-temporal databases, and web information retrieval. Chiang Lee received the B.S. degree from the National Cheng-Kung University, Taiwan, in 1980 and the M.E. and Ph.D. degrees in electrical engineering from the University of Florida, Gainesville, Florida, in 1986 and 1989, respectively. He joined IBM Mid-Hudson Laboratories, Kingston, NY in 1989 and participated in a project working on the design and performance analysis of a parallel and distributed database system. He joined the faculty of National Cheng-Kung University in 1990 and is currently a professor of the Department of Computer Science and Information Engineering of the university. His research interests are in the areas of mobile computing, sensor networks, and database systems. He has many papers published in major database journals and conferences, and has been invited as an author of a chapter for several technical books. Dr. Lee also served as a Steering Committee member of the DASFAA International Conference from 1996 to 1998, and served on organizing and program committee for several major international conferences. Lien-Fa Lin received his M.E. degree in the Department of Computer Science and Engineering at the Yuan Ze University, Taiwan, in 1993. Currently, he is a Ph.D. student of the Department of Computer Science and Information Engineering at the National Cheng-Kung University, Taiwan. His research interests include mobile/wireless data management, spatio-temporal databases, and web information retrieval.     

Hybrid Morphology Processing Unit Architecture for Moving Object Segmentation Systems

Video segmentation is a key operation in MPEG-4 content-based coding systems. For real-time applications, hardware implementation of video segmentation is inevitable. In this paper, we propose a hybrid morphology processing unit architecture for real-time moving object segmentation systems, where a prior effective moving object segmentation algorithm is implemented. The algorithm is first mapped to pixel-based operations and morphological operations, which makes the hardware implementation feasible. Then the high computation load, which is more than 4.2 GOPS, can be overcome with a dedicated morphology engine and a programmable morphology PE array. In addition, the hardware cost, memory size, and memory bandwidth can be reduced with the partial-result-reuse concept. This chip is designed with TSMC 0.35 μm 1P4M technology, and can achieve the processing speed of 30 QCIF frames or 7,680 morphological operations per second at 26 MHz. Simulation shows that the proposed hardware architecture is efficient in both hardware complexity and memory organization. It can be integrated into any content-based video processing and encoding systems. Shao-Yi Chien was born in Taipei, Taiwan, R.O.C., in 1977. He received the B.S. and Ph.D. degrees from the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, in 1999 and 2003, respectively. During 2003 to 2004, he was a research staff in Quanta Research Institute, Tao Yuan Shien, Taiwan. In 2004, he joined the Graduate Institute of Electronics Engineering and Department of Electrical Engineering, National Taiwan University, as an Assistant Professor. His research interests include video segmentation algorithm, intelligent video coding technology, image processing, computer graphics, and associated VLSI architectures. Bing-Yu Hsieh was born in Taichung, Taiwan, in 1979. He received the B.S.E.E and M.S.E.E degrees from National Taiwan University (NTU), Taipei, in 2001 and 2003, respectively. He joined MediaTek, Inc., Hsinchu, Taiwan, in 2003, where he develops integrated circuits related to multimedia systems and optical storage devices. His research interests include object tracking, video coding, baseband signal processing, and VLSI design. Yu-Wen Huang was born in Kaohsiung, Taiwan, in 1978. He received the B.S. degree in electrical engineering and Ph. D. degree in the Graduate Institute of Electronics Engineering from National Taiwan University (NTU), Taipei, in 2000 and 2004, respectively. He joined MediaTek, Inc., Hsinchu, Taiwan, in 2004, where he develops integrated circuits related to video coding systems. His research interests include video segmentation, moving object detection and tracking, intelligent video coding technology, motion estimation, face detection and recognition, H.264/AVC video coding, and associated VLSI architectures. Shyh-Yih Ma received the B.S.E.E, M.S.E.E, and Ph.D. degrees from National Taiwan University in 1992, 1994, and 2001, respectively. He joined Vivotek, Inc., Taipei County, in 2000, where he developed multimedia communication systems on DSPs. His research interests include video processing algorithm design, algorithm optimization for DSP architecture, and embedded system design. Liang-Gee Chen was born in Yun-Lin, Taiwan, in 1956. He received the BS, MS, and Ph.D degrees in Electrical Engineering from National Cheng Kung University, in 1979, 1981, and 1986, respectively. He was an Instructor (1981–1986), and an Associate Professor (1986–1988) in the the Department of Electrical Engineering, National Cheng Kung University. In the military service during 1987 and 1988, he was an Associate Professor in the Institute of Resource Management, Defense Management College. From 1988, he joined the Department of Electrical Engineering, National Taiwan University. During 1993 to 1994 he was Visiting Consultant of DSP Research Department, AT&T Bell Lab, Murray Hill. At 1997, he was the visiting scholar of the Department of Electrical Engineering, University, of Washington, Seattle. Currently, he is Professor of National Taiwan University. From 2004, he is also the Executive Vice President and the General Director of Electronics Research and Service Organization (ERSO) in the Industrial Technology Research Institute (ITRI). His current research interests are DSP architecture design, video processor design, and video coding system. Dr. Chen is a Fellow of IEEE. He is also a member of the honor society Phi Tan Phi. He was the general chairman of the 7th VLSI Design CAD Symposium. He is also the general chairman of the 1999 IEEE Workshop on Signal Processing Systems: Design and Implementation. He serves as Associate Editor of IEEE Trans. on Circuits and Systems for Video Technology from June 1996 until now and the Associate Editor of IEEE Trans. on VLSI Systems from January 1999 until now. He was the Associate Editor of the Journal of Circuits, Systems, and Signal Processing from 1999 until now. He served as the Guest Editor of The Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology, November 2001. He is also the Associate Editor of the IEEE Trans. on Circuits and Systems II: Analog and Digital Signal Processing. From 2002, he is also the Associate Editor of Proceedings of the IEEE. Dr. Chen received the Best Paper Award from ROC Computer Society in 1990 and 1994. From 1991 to 1999, he received Long-Term (Acer) Paper Awards annually. In 1992, he received the Best Paper Award of the 1992 Asia-Pacific Conference on Circuits and Systems in VLSI design track. In 1993, he received the Annual Paper Award of Chinese Engineer Society. In 1996, he received the Out-standing Research Award from NSC, and the Dragon Excellence Award for Acer. He is elected as the IEEE Circuits and Systems Distinguished Lecturer from 2001–2002.     

Effective Location Based Services with Dynamic Data Management in Mobile Environments

With the proliferation of mobile computing technologies, location based services have been identified as one of the most promising target application. We classify mobile information service domains based on feature characteristics of the information sources and different patterns of mobile information access. By carefully examining the service requirements, we identify the dynamic data management problem that must be addressed for effective location based services in mobile environments. We then devise a general architecture and cost model for servicing both location independent and location dependent data. Based on the architecture and cost model, we propose a set of dynamic data management strategies that employs judicious caching, proactive server pushing and neighborhood replication to reduce service cost and improve response time under changing user mobility and access patterns. Detail behavior analysis helps us in precisely capturing when and how to apply these strategies. Simulation results suggest that different strategies are effective for different types of data in response to different patterns of movement and information access. Shiow-yang Wu is an associate professor of the Department of Computer Science and Information Engineering at National Dong Hwa University, Hualien, Taiwan, R.O.C. He received the BS and MS degrees in computer engineering from National Chiao Tung University, Hsinchu, Taiwan, ROC, and the PhD degree in computer science from the University of Texas at Austin in 1984, 1986, and 1995, respectively. His research interests include data/knowledge bases, mobile computing, distributed processing, intelligence information systems, and electronic commerce. Kun-Ta Wu was born in Taipei, Taiwan, R.O.C., in 1976. He received the B.S. degree in computer science from Soochow University, Taipei, Taiwan, R.O.C., in 1999 and the M.S. degree in computer science and information engineering from National Dong Hwa University, Hualien, Taiwan, R.O.C., in 2001. Currently, he is an Assistant Researcher in the Domestic Division at Science and Technology Information Center, National Science Council, R.O.C., as a member of Information Gathering and Analysis Group of National Information and Communication Security Taskforce. His research interests include mobile computing, wireless network and information security.     

An On-Demand Routing Protocol with Backtracking for Mobile Ad Hoc Networks

A mobile ad hoc network (MANET) is characterized by multi-hop wireless links and frequent node mobility. Communication between non-neighboring nodes requires a multi-hop routing protocol to establish a route. But, the route often breaks due to mobility. The source must rediscover a new route for delivering the data packets. This wastes the resources that are limited in MANET. In this paper, a new on-demand routing protocol is proposed, named on-demand routing protocol with backtracking (ORB), for multi-hop mobile ad hoc networks. We use the multiple routes and cache data technique to reduce the rediscovery times and overhead. After executing the route discovery phase, we find out a set of nodes, named checkpoint, which has the multiple routes to the destination. When a checkpoint node receives a data packet, it caches this data packet in its buffer within a specific time period. When a node detects a broken route during the data packets delivery or receives an error packet, it will either recover the broken route or reply the error packet to the source. If a node can not forward the data packet to the next node, it replies an error packet to the source. This packet is backtracking to search a checkpoint to redeliver the data packet to the destination along other alternate routes. The main advantage of ORB is to reduce the flooding search times, maybe just delay and cost while a route has broken. The experimental results show that the proposed scheme can increase the performance of delivery but reduce the overhead efficiently comparing with that of AODV based routing protocols. Hua-Wen Tsai received the B.S. degree in Information Management from Chang Jung Christian University, Taiwan, in June 1998 and the M.B.A. degree in Business and Operations Management from Chang Jung Christian University, Taiwan, in June 2001. Since September 2001, he has been working towards the Ph.D. degree and currently is a doctoral candidate in the Department of Computer Science and Information Engineering, National Cheng Kung University, Taiwan. His research interests include wireless communication, ad hoc networks, and sensor networks. Tzung-Shi Chen received the B.S. degree in Computer Science and Information Engineering from Tamkang University, Taiwan, in June 1989 and the Ph.D. degree in Computer Science and Information Engineering from National Central University, Taiwan, in June 1994. He joined the faculty of the Department of Information Management, Chung Jung University, Tainan, Taiwan, as an Associate Professor in June 1996. Since November 2002, he has become a Full Professor at the Department of Information Management, Chung Jung University, Tainan, Taiwan. He was a visiting scholar at the Department of Computer Science, University of Illinois at Urbana-Champaign, USA, from June to September 2001. He was the chairman of the Department of Information Management at Chung Jung University from August 2000 to July 2003. Since August 2004, he has become a Full Professor at the Department of Information and Learning Technology, National University of Tainan, Tainan, Taiwan. Currently, he is the chairman of the Department of Information and Learning Technology, National University of Tainan. He co-received the best paper award of 2001 IEEE ICOIN-15. His current research interests include mobile computing and wireless networks, mobile learning, data mining, and pervasive computing. Dr. Chen is a member of the IEEE Computer Society. Chih-Ping Chu received the B.S. degree in agricultural chemistry from National Chung Hsing University, Taiwan, the M.S. degree in computer science from the University of California, Riverside, and the Ph.D. degree in computer science from Louisiana State University. He is currently a Professor in the Department of Computer Science and Information Engineering of National Cheng Kung University, Taiwan. His current research interests include parallel computing, parallel processing, component-based software development, and internet computing.     

The Coverage Problem in a Wireless Sensor Network

One of the fundamental issues in sensor networks is the coverage problem, which reflects how well a sensor network is monitored or tracked by sensors. In this paper, we formulate this problem as a decision problem, whose goal is to determine whether every point in the service area of the sensor network is covered by at least k sensors, where k is a given parameter. The sensing ranges of sensors can be unit disks or non-unit disks. We present polynomial-time algorithms, in terms of the number of sensors, that can be easily translated to distributed protocols. The result is a generalization of some earlier results where only k = 1 is assumed. Applications of the result include determining insufficiently covered areas in a sensor network, enhancing fault-tolerant capability in hostile regions, and conserving energies of redundant sensors in a randomly deployed network. Our solutions can be easily translated to distributed protocols to solve the coverage problem.A preliminary version of this paper has appeared in the Workshop on Wireless Sensor Networks and Applications, 2003, San Diego, CA, USA. Chi-Fu Huang received his B.S. and M.S. degrees both in Computer Science and Information Engineering from the Feng-Chia University and the National Central University in 1999 and 2001, respectively. He obtained his Ph.D. in the Department of Computer Science and Information Engineering from the National Chiao-Tung University in September of 2004. He is currently a Research Assistant Professor at the Department of Computer Science and Information Engineering, National Chiao-Tung University, Taiwan. His research interests include wireless communication and mobile computing, especially in ad hoc and sensor networks. Yu-Chee Tseng received his B.S. and M.S. degrees in Computer Science from the National Taiwan University and the National Tsing-Hua University in 1985 and 1987, respectively. He worked for the D-LINK Inc. as an engineer in 1990. He obtained his Ph.D. in Computer and Information Science from the Ohio State University in January of 1994. He was an Associate Professor at the Chung-Hua University (1994–1996) and at the National Central University (1996–1999), and a Full Professor at the National Central University (1999–2000). Since 2000, he has been a Full Professor at the Department of Computer Science and Information Engineering, National Chiao-Tung University, Taiwan. Dr. Tseng served as a Program Chair in the Wireless Networks and Mobile Computing Workshop, 2000 and 2001, as a Vice Program Chair in the Int’l Conf. on Distributed Computing Systems (ICDCS), 2004, as a Vice Program Chair in the IEEE Int’l Conf. on Mobile Ad-hoc and Sensor Systems (MASS), 2004, as an Associate Editor for The Computer Journal, as a Guest Editor for ACM Wireless Networks special issue on “Advances in Mobile and Wireless Systems”, as a Guest Editor for IEEE Transactions on Computers special on “Wireless Internet”, as a Guest Editor for Journal of Internet Technology special issue on “Wireless Internet: Applications and Systems”, as a Guest Editor for Wireless Communications and Mobile Computing special issue on “Research in Ad Hoc Networking, Smart Sensing, and Pervasive Computing”, as an Editor for Journal of Information Science and Engineering, as a Guest Editor for Telecommunication Systems special issue on “Wireless Sensor Networks”, and as a Guest Editor for Journal of Information Science and Engineering special issue on “Mobile Computing”. He is a two-time recipient of the Outstanding Research Award, National Science Council, ROC, in 2001–2002 and 2003–2005, and a recipient of the Best Paper Award in Int’l Conf. on Parallel Processing, 2003. Several of his papers have been chosen as Selected/Distinguished Papers in international conferences. He has guided students to participate in several national programming contests and received several awards. His research interests include mobile computing, wireless communication, network security, and parallel and distributed computing. Dr. Tseng is a member of ACM and a Senior Member of IEEE.This revised version was published online in August 2005 with a corrected cover date.     

Survey on Block Matching Motion Estimation Algorithms and Architectures with New Results

Block matching motion estimation is the heart of video coding systems. During the last two decades, hundreds of fast algorithms and VLSI architectures have been proposed. In this paper, we try to provide an extensive exploration of motion estimation with our new developments. The main concepts of fast algorithms can be classified into six categories: reduction in search positions, simplification of matching criterion, bitwidth reduction, predictive search, hierarchical search, and fast full search. Comparisons of various algorithms in terms of video quality and computational complexity are given as useful guidelines for software applications. As for hardware implementations, full search architectures derived from systolic mapping are first introduced. The systolic arrays can be divided into inter-type and intra-type with 1-D, 2-D, and tree structures. Hexagonal plots are presented for system designers to clearly evaluate the architectures in six aspects including gate count, required frequency, hard-ware utilization, memory bandwidth, memory bitwidth, and latency. Next, architectures supporting fast algorithms are also reviewed. Finally, we propose our algorithmic and architectural co-development. The main idea is quick checking of the entire search range with simplified matching criterion to globally eliminate impossible candidates, followed by finer selection among potential best matched candidates. The operations of the two stages are mapped to the same hardware for resource sharing. Simulation results show that our design is ten times more area-speed efficient than full search architectures while the video quality is competitively the same. Yu-Wen Huang was born in Kaohsiung, Taiwan, in 1978. He received the B.S. degree in electrical engineering and the Ph.D. degree in electronics engineering from National Taiwan University, Taipei, in June 2000 and December 2004, respectively. He joined MediaTek, Inc., Hsinchu, Taiwan, in 2004, where he develops integrated circuits related to video coding systems. His research interests include video segmentation, moving object detection and tracking, intelligent video coding technology, motion estimation, face detection and recognition, H.264/AVC video coding, and associated VLSI architectures. Ching-Yeh Chen was born in Taipei, Taiwan, in 1980. He received the B.S. degree from the Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan, in 2002. He currently is pursuing the Ph.D. degree at the Graduate Institute of Electronics Engineering, National Taiwan University. His research interests include intelligent video signal processing, global/local motion estimation, scalable video coding, and associated VLSI architectures. Chen-Han Tsai received the B.S. degree in electrical engineering from National Taiwan University in 2002. Now he is working toward the Ph.D. degree in the Graduate Institute of Electronics Engineering, National Taiwan University. His major research interests include face detection and recognition, motion estimation, H.264/AVC video coding, digital TV systems, and related VLSI architectures. Chun-Fu Shen received the B.S. and M.S. degrees in electrical engineering from National Taiwan University in 1996 and 1998, respectively. After two years of military service, he joined VIVOTEK, Inc., Taipei County, Taiwan, in 2000. He developed many video coding systems and IP camera products on DSP platforms and ASICs. His major research interests include JPEG, H.263, MPEG-4, and H.264/AVC coding systems, network camera SOC, and embedded systems. Liang-Gee Chen was born in Yun-Lin, Taiwan, in 1956. He received the B.S., M.S., and Ph.D. degrees in electrical engineering from National Cheng Kung University, in 1979, 1981, and 1986, respectively. He was an instructor (1981–1986), and an associate professor (1986–1988) in the Department of Electrical Engineering, National Cheng Kung University. In the military service during 1987 and 1988, he was an associate professor in the Institute of Resource Management, Defense Management College. From 1988, he joined the Department of Electrical Engineering, National Taiwan University. During 1993 to 1994 he was a visiting consultant of DSP Research Department, AT&T Bell Lab, Murray Hill. In 1997, he was the visiting scholar of the Department of Electrical Engineering, University, of Washington, Seattle. Currently, he is a professor of National Taiwan University. From 2004, he is also the executive vice president and the general director of Electronics Research and Service Organization (ERSO) in the Industrial Technology Research Institute (ITRI). His current research interests are DSP architecture design, video processor design, and video coding systems. Dr. Chen is a Fellow of IEEE. He is also a member of the honor society Phi Tau Phi. He was the general chairman of the 7th VLSI Design CAD Symposium. He was also the general chairman of the 1999 IEEE Workshop on Signal Processing Systems: Design and Implementation. He has served as the associate editor of IEEE Transactions on Circuits and Systems for Video Technology since 1996, the associate editor of IEEE Transactions on VLSI Systems since 1999, the associate editor of Journal of Circuits, Systems, and Signal Processing since 1999, and the guest editor of Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology since 2001. Now he is also the associate editor of IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing and the associate editor of Proceedings of the IEEE. Dr. Chen received the Best Paper Awards from ROC Computer Society in 1990 and 1994. From 1991 to 2005, he received Long-Term (Acer) Paper Awards annually. In 1992, he received the Best Paper Award of the 1992 Asia-Pacific Conference on Circuits and Systems in VLSI design track. In 1993, he received the Annual Paper Award of Chinese Engineer Society. In 1996, he received the Outstanding Research Award from National Science Council (NSC) and the Dragon Excellence Award from Acer. He was elected as the IEEE Circuits and Systems Distinguished Lecturer from 2001–2002.     

VLSI Architecture for Forward Discrete Wavelet Transform Based on B-spline Factorization

Based on B-spline factorization, a new category of architectures for Discrete Wavelet Transform (DWT) is proposed in this paper. The B-spline factorization mainly consists of the B-spline part and the distributed part. The former is proposed to be constructed by use of the direct implementation or Pascal implementation. And the latter is the part introducing multipliers and can be implemented with the Type-I or Type-II polyphase decomposition. Since the degree of the distributed part is usually designed as small as possible, the proposed architectures could use fewer multipliers than previous arts, but more adders would be required. However, many adders can be implemented with smaller area and lower speed because only few adders are on the critical path. Three case studies, including the JPEG2000 default (9, 7) filter, the (6, 10) filter, and the (10, 18) filter, are given to demonstrate the efficiency of the proposed architectures.Chao-Tsung Huang was born in Kaohsiung, Taiwan, R.O.C., in 1979. He received the B.S. degree from the Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan, R.O.C., in 2001. He currently is working toward the Ph.D. degree at the Graduate Institute of Electronics Engineering, National Taiwan University. His major research interests include VLSI design and implementation for signal processing systems.Po-Chih Tseng was born in Tao-Yuan, Taiwan in 1977. He received the B.S. degree in Electrical and Control Engineering from National Chiao Tung University in 1999 and the M.S. degree in Electrical Engineering from National Taiwan University in 2001. He currently is pursuing the Ph.D. degree at the Graduate Institute of Electronics Engineering, Department of Electrical Engineering, National Taiwan University. His research interests include VLSI design and implementation for signal processing systems, energy-efficient reconfigurable computing for multimedia systems, and power-aware image and video coding systems.Liang-Gee Chen received the B.S., M.S., and Ph.D. degrees in electrical engineering from National Cheng Kung University, Tainan, Taiwan, R.O.C., in 1979, 1981, and 1986, respectively.In 1988, he joined the Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan, R.O.C. During 1993–1994, he was a Visiting Consultant in the DSP Research Department, AT&T Bell Labs, Murray Hill, NJ. In 1997, he was a Visiting Scholar of the Department of Electrical Engineering, University of Washington, Seattle. Currently, he is Professor at National Taiwan University, Taipei, Taiwan, R.O.C. His current research interests are DSP architecture design, video processor design, and video coding systems.Dr. Chen has served as an Associate Editor of IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY since 1996, as Associate Editor of the IEEE TRANSACTIONS ON VLSI SYSTEMS since 1999, and as Associate Editor of IEEE TRANSACTIONS CIRCUITS AND SYSTEMS II since 2000. He has been the Associate Editor of the Journal of Circuits, Systems, and Signal Processing since 1999, and a Guest Editor for the Journal of Video Signal Processing Systems. He is also the Associate Editor of the PROCEEDINGS OF THE IEEE. He was the General Chairman of the 7th VLSI Design/CAD Symposium in 1995 and of the 1999 IEEE Workshop on Signal Processing Systems: Design and Implementation. He is the Past-Chair of Taipei Chapter of IEEE Circuits and Systems (CAS) Society, and is a member of the IEEE CAS Technical Committee of VLSI Systems and Applications, the Technical Committee of Visual Signal Processing and Communications, and the IEEE Signal Processing Technical Committee of Design and Implementation of SP Systems. He is the Chair-Elect of the IEEE CAS Technical Committee on Multimedia Systems and Applications, During 2001-2002, he served as a Distinguished Lecturer of the IEEE CAS Society. He received the Best Paper Award from the R.O.C. Computer Society in 1990 and 1994. Annually from 1991 to 1999, he received Long-Term (Acer) Paper Awards. In 1992, he received the Best Paper Award of the 1992 Asia-Pacific Conference on circuits and systems in the VLSI design track. In 1993, he received the Annual Paper Award of the Chinese Engineer Society. In 1996 and 2000, he received the Outstanding Research Award from the National Science Council, and in 2000, the Dragon Excellence Award from Acer. He is a member of Phi Tan Phi.