京都大学 / 新制・課程博士 / 博士(情報学) / 甲第23310号 / 情博第746号 / 新制||情||127(附属図書館) / 京都大学大学院情報学研究科知能情報学専攻 / (主査)教授 鹿島 久嗣, 教授 田中 利幸, 教授 山下 信雄 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

No description available.

No / A wireless sensor network is a network of large numbers of sensor nodes, where each sensor node is a tiny device that is equipped with a processing, sensing subsystem and a communication subsystem. The critical issue in wireless sensor networks is how to gather sensed data in an energy-efficient way, so that the network lifetime can be extended. The design of protocols for such wireless sensor networks has to be energy-aware in order to extend the lifetime of the network because it is difficult to recharge sensor node batteries. We propose a protocol to form clusters, select cluster heads, select cluster senders and determine appropriate routings in order to reduce overall energy consumption and enhance the network lifetime. Our clustering protocol is called an Efficient Cluster-Based Communication Protocol (ECOMP) for Wireless Sensor Networks. In ECOMP, each sensor node consumes a small amount of transmitting energy in order to reach the neighbour sensor node in the bidirectional ring, and the cluster heads do not need to receive any sensed data from member nodes. The simulation results show that ECOMP significantly minimises energy consumption of sensor nodes and extends the network lifetime, compared with existing clustering protocol.

<p>When researchers work on time series or sequence, certain fundamental questions will naturally arise. One of them will be whether the series or sequence exhibits a gradual trend over time. In this thesis, we propose a test statistic based on moving order statistics and establish an exact procedure to test for the presence of monotone trends. We show that the test statistic under the null hypothesis that there is no trend follows the closed skew normal distribution. An efficient algorithm is then developed to generate realizations from this null distribution. A simulation study is conducted to evaluate the proposed test under the alternative hypotheses with linear, logarithmic and quadratic trend functions. Finally, a practical example is provided to illustrate the proposed test procedure.</p> / Master of Science (MSc)

We consider a class of periodic preventive maintenance (PM) optimization problems, for a single piece of equipment that deteriorates with time or use, and can be repaired upon failure, through corrective maintenance (CM). We develop analytical and simulation-based optimization models that seek an optimal periodic PM policy, which minimizes the sum of the expected total cost of PMs and the risk-averse cost of CMs, over a finite planning horizon. In the simulation-based models, we assume that both types of maintenance actions are imperfect, whereas our analytical models consider imperfect PMs with minimal CMs. The effectiveness of maintenance actions is modeled using age reduction factors. For a repairable unit of equipment, its virtual age, and not its calendar age, determines the associated failure rate. Therefore, two sets of parameters, one describing the effectiveness of maintenance actions, and the other that defines the underlying failure rate of a piece of equipment, are critical to our models. Under a given maintenance policy, the two sets of parameters and a virtual-age-based age-reduction model, completely define the failure process of a piece of equipment. In practice, the true failure rate, and exact quality of the maintenance actions, cannot be determined, and are often estimated from the equipment failure history. We use a Bayesian approach to parameter estimation, under which a random-walk-based Gibbs sampler provides posterior estimates for the parameters of interest. Our posterior estimates for a few datasets from the literature, are consistent with published results. Furthermore, our computational results successfully demonstrate that our Gibbs sampler is arguably the obvious choice over a general rejection sampling-based parameter estimation method, for this class of problems. We present a general simulation-based periodic PM optimization model, which uses the posterior estimates to simulate the number of operational equipment failures, under a given periodic PM policy. Optimal periodic PM policies, under the classical maximum likelihood (ML) and Bayesian estimates are obtained for a few datasets. Limitations of the ML approach are revealed for a dataset from the literature, in which the use of ML estimates of the parameters, in the maintenance optimization model, fails to capture a trivial optimal PM policy. Finally, we introduce a single-stage and a two-stage formulation of the risk-averse periodic PM optimization model, with imperfect PMs and minimal CMs. Such models apply to a class of complex equipment with many parts, operational failures of which are addressed by replacing or repairing a few parts, thereby not affecting the failure rate of the equipment under consideration. For general values of PM age reduction factors, we provide sufficient conditions to establish the convexity of the first and second moments of the number of failures, and the risk-averse expected total maintenance cost, over a finite planning horizon. For increasing Weibull rates and a general class of increasing and convex failure rates, we show that these convexity results are independent of the PM age reduction factors. In general, the optimal periodic PM policy under the single-stage model is no better than the optimal two-stage policy. But if PMs are assumed perfect, then we establish that the single-stage and the two-stage optimization models are equivalent. / text

Combinatorial objects can be represented by strings, such as 21534 for the permutation (1 2) (3 5 4), or 110100 for the binary tree corresponding to the balanced parentheses (()()). Given a string s = s1 s2 sn, the right-shift operation shift(s, i, j) replaces the substring si si+1..sj by si+1..sj si. In other words, si is right-shifted into position j by applying the permutation (j j−1 .. i) to the indices of s. Right-shifts include prefix-shifts (i = 1) and adjacent-transpositions (j = i+1). A fixed-content language is a set of strings that contain the same multiset of symbols. Given a fixed-content language, a shift Gray code is a list of its strings where consecutive strings differ by a shift. This thesis asks if shift Gray codes exist for a variety of combinatorial objects. This abstract question leads to a number of practical answers. The first prefix-shift Gray code for multiset permutations is discovered, and it provides the first algorithm for generating multiset permutations in O(1)-time while using O(1) additional variables. Applications of these results include more efficient exhaustive solutions to stacker-crane problems, which are natural NP-complete traveling salesman variants. This thesis also produces the fastest algorithm for generating balanced parentheses in an array, and the first minimal-change order for fixed-content necklaces and Lyndon words. These results are consequences of the following theorem: Every bubble language has a right-shift Gray code. Bubble languages are fixed-content languages that are closed under certain adjacent-transpositions. These languages generalize classic combinatorial objects: k-ary trees, ordered trees with fixed branching sequences, unit interval graphs, restricted Schr oder and Motzkin paths, linear-extensions of B-posets, and their unions, intersections, and quotients. Each Gray code is circular and is obtained from a new variation of lexicographic order known as cool-lex order. Gray codes using only shift(s, 1, n) and shift(s, 1, n−1) are also found for multiset permutations. A universal cycle that omits the last (redundant) symbol from each permutation is obtained by recording the first symbol of each permutation in this Gray code. As a special case, these shorthand universal cycles provide a new fixed-density analogue to de Bruijn cycles, and the first universal cycle for the "middle levels" (binary strings of length 2k + 1 with sum k or k + 1).