两台恒速机上的MapReduce排序算法研究

研究源自于MapReduce系统的一类排序问题。给定两台恒速机和一组按列表到达的工件，每个工件包含两类任务：Map Task和Reduce Task。假设Map任务和Reduce任务都是不可中断的，Map任务可以并行处理，即可以任意分割成若干小的任务并在两台机器上同时处理，而Reduce任务只可以在单台机器上处理。一旦工件到达，必须为其指派机器和开工时间，目标是使得最后完工时间最小。对LSc算法的竞争比进行了分析，得到其一般情形下的竞争比当$s\geq（1+\sqrt{5}）/2$时为$1+1/s$，否则为$1+s/（s+1）$。而当每个工件$J_j$都满足其Map任务总长大于等于Reduce任务总长时，其竞争比当$s\geq（1+\sqrt{3}）/2$时不超过$1+1/（2s）$，否则为不超过$1+s/（2s+1）$。     

IEC／EN 60598-1灯具标准2008版的更新

文内介绍了2008年出版的灯具通用标准安全要求标准IEC／EN 60598-1的最新交化，分析了可能涉及重新测试的改动部分，也阐述了不涉及重新测试的修改，期望能给灯具业界提供一个参考。     

Design and Analysis of Optimal Multi-Level Hierarchical Mobile IPv6 Networks

Hierarchical Mobile IPv6 (HMIPv6) is an enhanced version of Mobile IPv6 designed to reduce signaling overhead and to support seamless handoff in IP-based wireless/mobile networks. To support more scalable services, HMIPv6 networks can be organized as the form of a multi-level hierarchy architecture (i.e., tree structure). However, since multi-level HMIPv6 networks incur additional packet processing overhead at multiple mobility agents, it is important to find the optimal hierarchy level to minimize the total cost, which consists of the location update cost and the packet delivery cost. In this paper, we investigate this problem, namely the design of an optimal multi-level HMIPv6 (OM-HMIPv6) network. To accomplish this, we design a function to represent the location update cost and the packet delivery cost in multi-level HMIPv6 networks. Based on these formulated cost functions, we calculate the optimal hierarchy level in multi-level HMIPv6 networks, in order to minimize the total cost. In addition, we investigate the effects of the session-to-mobility ratio (SMR) on the total cost and the optimal hierarchy. The numerical results, which show various relationships among the network size, optimal hierarchy, and SMR, can be utilized to design an optimal HMIPv6 network. In addition, the analytical results are validated by comprehensive simulations. Sangheon Pack received his B.S. (2000, magna cum laude) and Ph.D. (2005) degrees from Seoul National University, both in computer engineering. He is a post doctor fellow in the School of Computer Science and Engineering at the Seoul National University, Korea. He is a member of the IEEE and ACM. During 2002–2005, he was a recipient of the Korea Foundation for Advanced Studies (KFAS) Computer Science and Information Technology Scholarship. He has been also a member of Samsung Frontier Membership (SFM) from 1999. He received a student travel grant award for the IFIP Personal Wireless Conference (PWC) 2003. He was a visiting researcher to Fraunhofer FOKUS, German in 2003. His research interests include mobility management, wireless multimedia transmission, and QoS provision issues in the next-generation wireless/mobile networks. Yanghee Choi received B.S. in electronics engineering from Seoul National University, M.S. in electrical engineering from Korea advanced Institute of Science, and Doctor of Engineering in Computer Science from Ecole Nationale Superieure des Telecommunications (ENST) in Paris, in 1975, 1977 and 1984 respectively. Before joining the School of Computer Engineering, Seoul National University in 1991, he has been with Electronics and Telecommunications Research Institute (ETRI) during 1977–1991, where he served as director of Data Communication Section, and Protocol Engineering Center. He was research student at Centre National d'Etude des Telecommunications (CNET), Issy-les-Moulineaux, during 1981–1984. He was also Visiting Scientist to IBM T.J. Watson Research Center for the year 1988–1989. He is now leading the Multimedia Communications Laboratory in Seoul National University. He is also director of Computer Network Research Center in Institute of Computer Technology (ICT). He was editor-in-chief of Korea Information Science Society journals. He was chairman of the Special Interest Group on Information Networking. He has been associate dean of research affairs at Seoul National University. He was president of Open Systems and Internet Association of Korea. His research interest lies in the field of multimedia systems and high-speed networking. Minji Nam received her B.S. and M.S degrees in Computer Science and Engineering from Seoul National University in 2003 and 2005, respectively. From 2005, she has worked on Portable Internet Development Team for Korea Telecom. Her research interests are mobile networks, portable internet technology (IEEE 802.16) and Mobile IPv6.     

Some remarks on the symmetric rank-one update

We consider the symmetric rank-one, quasi-Newton formula. The hereditary properties of this formula do not require quasi-Newton directions of search. Therefore, this formula is easy to use in constrained optimization algorithms; no explicit projections of either the Hessian approximations or the parameter changes are required. Moreover, the entire Hessian approximation is available at each iteration for determining the direction of search, which need not be a quasi-Newton direction. Theoretical difficulties, however, exist. Even for a positive-definite, quadratic function with no constraints, it is possible that the symmetric rank-one update may not be defined at some iteration. In this paper, we first demonstrate that such failures of definition correspond to either losses of independence in the directions of search being generated or to near-singularity of the Hessian approximation being generated. We then describe a procedure that guarantees that these updates are well-defined for any nonsingular quadratic function. This procedure has been incorporated into an algorithm for minimizing a function subject to box constraints. Box constraints arise naturally in the minimization of a function with many minima or a function that is defined only in some subregion of the space.     

衬底对Cu(In,Ga)Se2薄膜织构的影响

分别在苏打石灰玻璃、Mo箔、无择优取向的Mo薄膜以及(110)择优取向的Mo薄膜四种不同衬底上，采用共蒸发工艺沉积约2 μm厚的Cu(In,Ga)Se₂薄膜，用X射线衍射仪测量薄膜的织构，研究衬底对Cu(In,Ga)Se₂薄膜织构的影响.在以上四种衬底上沉积的Cu(In,Ga)Se₂薄膜的(112)衍射峰强度依次逐渐减弱，(220/204)衍射峰从无到有且强度逐渐增强.在苏打石灰玻璃和Mo箔衬底上的Cu(In,Ga)Se_{2关键词： 择优取向 Cu(In 2}薄膜')" href="#">Ga)Se₂薄膜 太阳电池     

Residual Synchronization Error Elimination in OFDM Baseband Receivers

It is well known that an OFDM receiver is vulnerable to synchronization errors. Despite fine estimations used in the initial acquisition, there are still residual synchronization errors. Though these errors are very small, they severely degrade the bit error rate (BER) performance. In this paper, we propose a residual error elimination scheme for the digital OFDM baseband receiver aiming to improve the overall BER performance. Three improvements on existing schemes are made: a pilot‐aided recursive algorithm for joint estimation of the residual carrier frequency and sampling time offsets; a delay‐based timing error correction technique, which smoothly adjusts the incoming data stream without resampling disturbance; and a decision‐directed channel gain update algorithm based on recursive least‐squares criterion, which offers faster convergence and smaller error than the least‐mean‐squares algorithms. Simulation results show that the proposed scheme works well in the multipath channel, and its performance is close to that of an OFDM system with perfect synchronization parameters.     

掺Sn的In2O3透明导电膜生长优先取向对其光电性能的影响

采用反应热蒸发法制备掺Sn的In2O3(ITO)透明导电膜,系统研究了ITO薄膜生长的优先取向对其光电性能的影响.结果表明,ITO薄膜(400)取向的优先生长对其透过率影响很小,但可明显增加载流子迁移率,从而有效降低了薄膜的方块电阻.在两个相同的薄膜硅/单晶硅太阳能电池上分别沉积(222)和(400)ITO优先取向膜,光电转换效率分别为10.3%和12.9%,表明(400)取向更有利于提高电池效率.经优化,最佳衬底温度(Ts)为225℃,最佳氧流量(fO2)为4sccm.在优化的沉积条件下制备ITO薄膜,其电阻率可达到4.8×10-4Ω·cm,可见波段的透过率大于90%,性能指数为3.8×10-2□/Ω.     

基于802.11r漫游性能优化的WLAN建设

采用高级安全策略的无线网络在漫游时要忍受较大的时延,在不牺牲安全性的前提下快速灵活地漫游于无线局域之间成了无线局域网搭建的重中之重。基于IEEE 802.11r协议的快速BSS切换协议,以及对密钥结构和认证过程的较大改动,采用三层漫游技术实现了能够无缝漫游的校园无线网络,经过近1年的运营证明,该文提出的方案切实有效。     

基于二进制转换的0—1规划隐枚举法

本针对常规隐枚举法，提出了一种基于二进制转换的快速有效枚举出所有可能解的方法，包括旨在加速优化过程的所有可能解的排列规则，并给出了一个算例。     

Defining and optimizing algorithms for neighbouring particle identification in SPH fluid simulations

Lagrangian particle methods such as smoothed particle hydrodynamics (SPH) are very demanding in terms of computing time for large domains. Since the numerical integration of the governing equations is only carried out for each particle on a restricted number of neighbouring ones located inside a cut‐off radius r_c, a substantial part of the computational burden depends on the actual search procedure; it is therefore vital that efficient methods are adopted for such a search. The cut‐off radius is indeed much lower than the typical domain's size; hence, the number of neighbouring particles is only a little fraction of the total number. Straightforward determination of which particles are inside the interaction range requires the computation of all pair‐wise distances, a procedure whose computational time would be unpractical or totally impossible for large problems. Two main strategies have been developed in the past in order to reduce the unnecessary computation of distances: the first based on dynamically storing each particle's neighbourhood list (Verlet list) and the second based on a framework of fixed cells. The paper presents the results of a numerical sensitivity study on the efficiency of the two procedures as a function of such parameters as the Verlet size and the cell dimensions. An insight is given into the relative computational burden; a discussion of the relative merits of the different approaches is also given and some suggestions are provided on the computational and data structure of the neighbourhood search part of SPH codes. Copyright © 2008 John Wiley & Sons, Ltd.