Faculty Profiles - FUNABIKI Nobuo

MISC - FUNABIKI Nobuo

Division display 501 - 520 of about 573 ／ All the affair displays >>

A Proposal of a Two-Stage Approximation Algorithm for Link Scheduling Problems in Radio Networks

TAJIMA Shigeto, FUNABIKI Nobuo, HIGASHINO Teruo

IEICE technical report. Theoretical foundations of Computing 99 ( 724 ) 65 - 72 2000.3

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

In a multihop radio network, packets are transmitted from source nodes to destination nodes by activating connected links between them. Each node can either send a packet to or receive a packet from at most one of its adjacent nodes simultaneously. In order to minimize the transmission time for given requests, the problems must be solved of selecting a transmission route for each request (the routing problem) and of finding a link schedule (the link scheduling problem). In this paper, we propose a two-stage approximation algorithm for the link scheduling problem. The link scheduling problem is composed of SAS to satisfy the sequence of link activations and NAS not to satisfy it. We verify the performance through simulations for NAS and SAS, where our algorithm finds better solutions in shorter time than the existing algorithms.

CiNii Article

CiNii Books

researchmap

A three-stage heuristic combined neural-network algorithm for channel assignment in cellular mobile systems

N Funabiki, N Okutani, S Nishikawa

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 49 ( 2 ) 397 - 403 2000.3

Language：English Publisher：IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC

A three-stage algorithm of combining sequential heuristic methods into a parallel neural network is presented for the channel assignment problem in cellular mobile communication systems in this paper. The goal of this NP-complete problem is to find a channel assignment to requested calls with the minimum number of channels subject to interference constraints between channels. The three-stage algorithm consists of: 1) the regular interval assignment stage; 2) the greedy assignment stage; and 3) the neural-network assignment stage. In the first stage, the calls in a cell determining the lower bound on the total number of channels are assigned channels at regular intervals. In the second stage, the calls in a cell with the largest degree and its adjacent cells are assigned channels by a greedy heuristic method. In the third stage, the calls in the remaining cells are assigned channels by a binary neural network, The performance is verified through solving well-known benchmark problems, Especially for Sivarajan's benchmark problems, our three-stage algorithm first achieves the lower bound solutions in all of the 13 instances, while the computation time is comparable with existing algorithms.

DOI： 10.1109/25.832970

Web of Science

researchmap

無線通信網における信頼度制約通信経路割当問題に対するニューラルネットワーク併用二段階解法の提案

馬場孝之, 船曵信生, 田島滋人

電子情報通信学会論文誌A 2000

A three-stage heuristic combined neural-network algorithm for channel assignment in cellular mobile systems

Nobuo Funabiki, Noriko Okutani, Seishi Nishikawa

IEEE Transactions on Vehicular Technology 49 ( 2 ) 397 - 403 2000

Language：English

A three-stage algorithm of combining sequential heuristic methods into a parallel neural network is presented for the channel assignment problem in cellular mobile communication systems in this paper. The goal of this NP-complete problem is to find a channel assignment to requested calls with the minimum number of channels subject to interference constraints between channels. The three-stage algorithm consists of: 1) the regular interval assignment stage
2) the greedy assignment stage
and 3) the neural-network assignment stage. In the first stage the calls in a cell determining the lower bound on the total number of channels are assigned channels at regular intervals. In the second stage the calls in a cell with the largest degree and its adjacent cells are assigned channels by a greedy heuristic method. In the third stage the calls in the remaining cells are assigned channels by a binary neural network. The performance is verified through solving well-known benchmark problems. Especially for Sivarajan's benchmark problems our three-stage algorithm first achieves the lower bound solutions in all of the 13 instances while the computation time is comparable with existing algorithms. © 2000 IEEE.

DOI： 10.1109/25.832970

Scopus

researchmap

A three-stage heuristic combined neural-network algorithm for channel assignment in cellular mobile systems

Nobuo Funabiki, Noriko Okutani, Seishi Nishikawa

IEEE Transactions on Vehicular Technology 49 ( 2 ) 397 - 403 2000

Language：English

A three-stage algorithm of combining sequential heuristic methods into a parallel neural network is presented for the channel assignment problem in cellular mobile communication systems in this paper. The goal of this NP-complete problem is to find a channel assignment to requested calls with the minimum number of channels subject to interference constraints between channels. The three-stage algorithm consists of: 1) the regular interval assignment stage
2) the greedy assignment stage
and 3) the neural-network assignment stage. In the first stage the calls in a cell determining the lower bound on the total number of channels are assigned channels at regular intervals. In the second stage the calls in a cell with the largest degree and its adjacent cells are assigned channels by a greedy heuristic method. In the third stage the calls in the remaining cells are assigned channels by a binary neural network. The performance is verified through solving well-known benchmark problems. Especially for Sivarajan's benchmark problems our three-stage algorithm first achieves the lower bound solutions in all of the 13 instances while the computation time is comparable with existing algorithms. © 2000 IEEE.

DOI： 10.1109/25.832970

Scopus

researchmap

A greedy digital neural-network algorithm for subgraph isomorphism problems

Nobuo Funabiki, Teruo Higashino

Proc. of World Multiconference on Systemics, Cybernetics, and Informatics 2000

A greedyneural combined discrete optimization algorithm for triangle and Kn-subgraph partition problem

OHTSUKA H.

Proc. World Multiconference on Systemics, Cybernetics and Informatics (SCI2000) 12 557 - 562 2000

A proposal of a neuron filter algorithm with a thinning-out method for total coloring problems

Yoichi Takenaka, Nobuo Funabiki

Proc. of World Multiconference on Systemics, Cybernetics, and Informatics 2000

遺伝的プログラミングを用いた関数合成アルゴリズムの改良法の提案

関岡哲也, 船曵信生, 東野輝夫

電子情報通信学会論文誌D1 2000

静的マルチキャストルーティング問題に対する２段階解法の提案

藤井雅和, 船曵信生, 東野輝夫

第13回回路とシステム(軽井沢)ワークショップ講演集 2000

A two-stage discrete optimization method for largest common subgraph problems

N Funabiki, J Kitamichi

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E82D ( 8 ) 1145 - 1153 1999.8

Language：English Publisher：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG

A novel combinatorial optimization algorithm called 2-stage discrete optimization method (2DOM) is proposed for the largest common subgraph problem (LCSP) in this paper. Given two graphs G = (V-1, E-1) and H = (V-2, E-2), the goal of LCSP is to find a subgraph G' = (V-1', E-1') of G and a subgraph H' = (V-2', E-2') of H such that G' and H' are not only isomorphic to each other but also their number of edges is maximized. The two graphs G' and H' are isomorphic when \V-1'\ = \V-2'\ and \E-1'\ = \E-2'\, and there exists one-to-one vertex correspondence f : V-1' --> V-2' such that {u, v} is an element of E-1' if and only if {f(u), f(v)} is an element of E-2'. LCSP is known to be NP-complete in general. The 2DOM consists of a construction stage and a refinement stage to achieve the high solution quality and the short computation time for large size difficult combinatorial optimization problems. The construction stage creates a feasible initial solution with considerable quality, based on a greedy heuristic method. The refinement stage improves it keeping the feasibility, based on a random discrete descent method. The performance is evaluated by solving two types of randomly generated 1200 LCSP instances with a maximum of 500 vertices for G and 1000 vertices for H. The simulation result shows the superiority of 2DOM to the simulated annealing in terms of the solution quality and the computation time.

A gradual neural network approach for FPGA segmented channel routing problems

N Funabiki, M Yoda, J Kitamichi, S Nishikawa

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS 29 ( 4 ) 481 - 489 1999.8

Language：English Publisher：IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC

A novel neural network approach called gradual neural network (GNN) is presented for segmented channel routing in field programmable gate arrays (FPGA's). FPGA's contain predefined segmented channels for net routing, where adjacent segments in a track can be interconnected through programmable switches for longer segments. The goal of the FPGA segmented channel routing problem, known to be NP-complete, is to find a conflict-free net routing with the minimum routing cost. The GNN for the N-net-M-track problem consists of a neural network of N x M binary neurons and a gradual expansion scheme. The neural network satisfies the constraints of the problem, while the gradual expansion scheme seeks the cost minimization by gradually increasing activated neurons. The energy function and the motion equation are newly defined with heuristic methods, The performance is verified through solving 30 instances, where GNN finds better solutions than existing algorithms within a constant number of iteration steps.

DOI： 10.1109/3477.775264

Web of Science

researchmap

A gradual neural network approach for FPGA segmented channel routing problems

Nobuo Funabiki, Makiko Yoda, Junji Kitamichi, Seishi Nishikawa

IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 29 ( 4 ) 481 - 489 1999.8

Language：English

A novel neural network approach called gradual neural network (GNN) is presented for segmented channel routing in field programmable gate arrays (FPGA's). FPGA's contain predefined segmented channels for net routing, where adjacent segments in a track can be interconnected through programmable switches for longer segments. The goal of the FPGA segmented channel routing problem, known to be NP-complete, is to find a conflict-free net routing with the minimum routing cost. The GNN for the N-net-M-track problem consists of a neural network of N x M binary neurons and a gradual expansion scheme. The neural network satisfies the constraints of the problem, while the gradual expansion scheme seeks the cost minimization by gradually increasing activated neurons. The energy function and the motion equation are newly defined with heuristic methods. The performance is verified through solving 30 instances, where GNN finds better solutions than existing algorithms within a constant number of iteration steps. © 1999 IEEE.

DOI： 10.1109/3477.775264

Scopus

researchmap

A gradual neural network approach for FPGA segmented channel routing problems

Nobuo Funabiki, Makiko Yoda, Junji Kitamichi, Seishi Nishikawa

IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 29 ( 4 ) 481 - 489 1999.8

Language：English

A novel neural network approach called gradual neural network (GNN) is presented for segmented channel routing in field programmable gate arrays (FPGA's). FPGA's contain predefined segmented channels for net routing, where adjacent segments in a track can be interconnected through programmable switches for longer segments. The goal of the FPGA segmented channel routing problem, known to be NP-complete, is to find a conflict-free net routing with the minimum routing cost. The GNN for the N-net-M-track problem consists of a neural network of N x M binary neurons and a gradual expansion scheme. The neural network satisfies the constraints of the problem, while the gradual expansion scheme seeks the cost minimization by gradually increasing activated neurons. The energy function and the motion equation are newly defined with heuristic methods. The performance is verified through solving 30 instances, where GNN finds better solutions than existing algorithms within a constant number of iteration steps. © 1999 IEEE.

DOI： 10.1109/3477.775264

Scopus

researchmap

A gradual neural network algorithm for broadcast scheduling problems in packet radio networks

N Funaibiki, J Kitamichi

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E82A ( 5 ) 815 - 824 1999.5

Language：English Publisher：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG

A novel combinatorial optimization algorithm called "Gradual neural network (GNN)" is presented for NP-complete broadcast scheduling problems in packet radio (PR) networks. A PR network provides data communications services to a set of geographically distributed nodes through a common radio channel. A time division multiple access (TDMA) protocol is adopted for conflict-free communications, where packets are transmitted in repetition of fixed-length time-slots called a TDMA cycle. Given a PR network, the goal of GNN is to find a TDMA cycle with the minimum delay time for each node to broadcast packets. GNN for the N-node-M-slot TDMA cycle problem consists of a neural network with N x M binary neurons and a gradual expansion scheme. The neural network not only satisfies the constraints but also maximizes transmissions by two energy functions, whereas the gradual expansion scheme minimizes the cycle length by gradually expanding the size of the neural network. The performance is evaluated through extensive simulations in benchmark instances and in geometric graph instances with up to 1000 vertices, where GNN always finds better TDMA cycles than existing algorithms. The result in this paper supports the credibility of our GNN algorithm for a class of combinatorial optimization problems.

"A gradual neural network approach for broadcast scheduling in packet radio networks"

*Nobuo Funabiki, Junji Kitamichi

IEICE Transactions on Fundamentals E-82-A ( 5 ) 815 - 824 1999.5

A Proposal of an Improved Function Synthesis Algorithm with Genetic Programming

SEKIOKA TETSUYA, FUNABIKI NOBUO

IEICE technical report. Nonlinear problems 98 ( 663 ) 9 - 16 1999.3

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

The function synthesis problem for an unknown system requires to produce an approximate function which satisfies the relationships of given input and output data sets of the system. This problem is essential for the proper control of the system. When the system has the non-linearity characteristics, this problem becomes very difficult where the number of combinations of variables, constants, and operators quickly increases the computational complexity. This paper presents three improved methods for the genetic programming algorithm which is one of the function synthesis methods. They are the gradual expansion of function trees, the constant optimization by a local search, and the partial structure fixation of function trees based on the characteristics of the target system. The performance evaluation through the two-spirals problem and the sunspot prediction problem shows the effectiveness of the proposed three methods.

CiNii Article

CiNii Books

researchmap

A proposal of a neural network algorithm for route assignment problems with reliability in multihop radio networks

BABA Takayuki, FUNABIKI Nobuo

IEICE technical report. Nonlinear problems 98 ( 583 ) 17 - 24 1999.2

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

A multihop radio network is a large communication network between many nodes distributed around wide areas. Through a radio channel, each node can either send a packet to, or receive a packet from, at most one of its adjacent nodes simultaneously. Packets are transmitted from source nodes to destination nodes by activating several links between these nodes. In order to maximize the throughput or minimize the transmission time for given transmission requests, it is required to assign a transmission route and a link activation schedule for each request. In this network, each node has is different reliability to perform its function properly depending on the difference of running period, design specification, and environment. In this paper, we propose a two-stage algorithm to assign routes whose reliabilities are more than the specified threshold. This algorithm is composed of the iterated candidate extraction method with reliability satisfaction to extract route candidates and the greedy neural network algorithm to select a route to minimize a cost among plural candidates. Through simulations up to-500-node networks, we verify that our algorithm finds good solutions effectively.

CiNii Article

CiNii Books

researchmap

Formal verification method for combinatorial circuits at high level design

J Kitamichi, H Kageyama, N Funabiki

PROCEEDINGS OF ASP-DAC '99 319 - 322 1999

Language：English Publisher：IEEE

In this paper, we propose a formal verification method for combinatorial circuits at high level design. The specification is described by both integer and Boolean variables for input and output variables, and the implementation is described by only Boolean variables. Our verification method judges the equivalence between the specification and the implementation by deciding the truth of Presburger sentence. We show experimental results on some benchmarks, such as 4bit ALU, multiplier, by our method.

Web of Science

researchmap

プレスブルガー文真偽判定アルゴリズムのためのBDDの応用とそれを用いた回路検証

景山洋行, 北道淳司, 船曵信生

情報処理学会論文誌 1999

　 PREV - NEXT 　

< FUNABIKI Nobuo >

MISC - FUNABIKI Nobuo