Archive for January, 2012

Scalable extension of the H.264/AVC video coding standard

The main idea behind the scalable extension of H.264/AVC is to take the block based hybrid video
coding scheme one step further and achieve spatiotemporal and signal-to-noise-ratio (SNR)
scalability. The term scalability in the video coding context means that physically meaningful
video information can be recovered by decoding only a portion of the compressed bit stream.
For example, one should be able to recover from the compressed bit stream a video with lower
resolution than the original by decoding only the lowest spatial layer and discarding other
spatial layers. In SVC, scalability is achieved by taking advantage of the layered approach.
The structure of the encoding depends on which kind of scalability is needed. For example, Figure 1
depicts the block diagram of an SVC encoder with two spatial layers, which contain additional
SNR enhancement layers.

In each spatial layer hierarchical motion compensation and prediction is made. The redundancy
between adjacent pictures and layers is based on interand intraprediction techniques. After
motion compensated prediction, transform coding is applied using the same transformation
techniques as in the H.264/AVC standard. SNR and quality scalability is achieved by coding the
difference between transformed and not transformed slices using progressive coding. These
progressively coded slices can then be truncated at any position within each slice thus improving
the userperceived visual quality proportional to the number of bits included in the truncated
slice. Mean while, temporal scalability is achieved using hierarchical B pictures, which provide a
predictive structure already included in H.264/AVC. Motion compensated temporal filtering can also
be used but it is, for the time being, included as a non-normative option only for achieving
temporal scalability. An example of hierarchical coding structure for group of pictures (GOP)
which length is eight pictures is illustrated in Figure 2. All of these scalability modes can be
combined to achieve three dimensional (spatial, temporal and SNR) scalability.

Figure 1: Block diagram for the H.264 scalable extension

Figure 2: Hierarchical GOP structure

The dependency between layers in scalable video coding

Layers in scalable video coding are classified as a base layer and enhancement layer(s). In SVC, the
base layer can be decoded using a standard H.264/AVC decoder. Information from lower layers is used
to remove the redundancy between different layers. This increases coding efficiency but it also
increases the importance of the lowest layers during decoding process and reduce error resiliency.
If the base layer or one of the most important layers is lost, less important layers are useless
because decoding them requires redundant data from the most important layers. The dependency between
layers makes the prioritization of different layers during transmission suitable. The base layer
also usually needs less transmission bandwidth than the enhancement layers, which is also quite
important when allocating resources to different prioritization classes. Based on the SVC layer
prioritization suitability we propose a mechanism for adapting the video transmission to rapidly
changing wireless channel and network conditions. One of the main requirements for the architecture
is to be general enough to work with different access networks from IEEE 802.11 (WiFi) and
IEEE 802.16 (WiMAX) to 3GPP and UMTS.

, , , , , , , , , , , ,

Leave a comment

E-negotiation system based on intelligent architecture

E-negotiation process model and protocol provide plausible method for negotiation systems and remove
additional activities of the system. The model with activities related to every phase presented in
“Fig.1”. Negotiation process model is formed by goal driven negotiation and requirements assigned to
agents. Based on view point, agents are able to improve their behaviors over time. In that way, they
may get better with experiences at selecting and achieving goals by taking correct actions. So agents
can take proactive and reactive negotiation actions.
Now a day’s, because in e-market there are infinite participants, exponentially growing amount of
information available, information transparency, information overloading, different negotiation
mechanism price wars between buyers and between sellers and complexity of modern business trade
, therefore intelligent agent based automated negotiation systems are hopeful technologies that
play an important role. Intelligent agents systems can adopt various mechanisms (e.g. bidding,
auction, bargaining, and arbitration), information discovery and collection, negotiator selection,
proposal generation and evaluation, play of advisor and provide effective suggestion, fully
understand of owner requirements and preferences, coordinate interdependent relationships between
various negotiations, build comprehensive user models and finally the systems can make trust between
both users. In addition, intelligent agents allow negotiator to play both roles of buyer and seller
at the same time. Our proposed design has considered the notations and results of this research show
that proposed intelligent agent architecture would reduce negotiation time and provide rapid response
for their owners. Next step, we explain the particular design of intelligent agent’s architecture.
In order to explain the architecture, first we have to illustrate types of agents employed in the
architecture and then we show buyer and seller agent architecture.

Figure 1. Negotiation process model and assigns different activities to them

Figure 2. Buyer Agent Architecture based on Intelligent Agents

Figure 3.Seller Agent Architecture based on Intelligent Agents

In purposed model, Owner profile agent is to present owner goals, and aid the negotiator deciding on
goals and strategies. In addition, agents of this type would be able to adapt to the changes based on
owner behavior in the process of negotiations. Searcher Agent is an agent that searches potential
buyers or sellers that are in other distributed environments and performs the role of managing,
querying, or collating information from many distributed sources. A simple rule matching mechanism is
developed to extract relevant negotiator information from the search results. This agent also performs
post processing for the retrieved items and gives a list of qualified buyers or sellers with the
offer. Information mediator agent would envelope in actively searching, fetching, filtering, and
delivering information relevant to the issues from market knowledge base. Also this agent type is
able to identify the objectives, preferences and strategies of the opponent. Recommender agent is
able to generate a set of likely offers to be considered for submission to the opponent. The proposed
of advisor agent is to evaluate the offers received from the opponent and provide a feedback on the
defect and, possibly benefits of these offers. Negotiator agent is responsible for negotiating with
potential buyers or sellers, with respect to the preferences that have been collected from a group of
participants. Here, the goal is to bargaining with candidate sellers or buyers for the best offer
that satisfies the most demands and preferences of group members. In addition, this agent may be
capable of conducting negotiations by itself in a semi-autonomous or fully autonomous mode.
Applicability of full automation depends on the degree of certainty in objectives, preferences, and
tactics of the negotiator therefore the agent is an agent that optimizes the buyer or seller utility
based upon the requirements from owners’ requirements and constraints.Buyer or seller mediator agent
is an agent that delivers the status messages of active services between negotiators agents, and
between peer agents. In addition, this agent can play a role of an expert agent and in a sense; the
agent is an intelligent administrator agent.

, , , , , , , , , ,

Leave a comment

Computer Network Routing with a Fuzzy Neural Network

As more individuals transmit data through a computer network, the quality of service received by the users
begins to degrade. A major aspect of computer networks that is vital to quality of service is data routing.
A more effective method for routing data through a computer network can assist with the new problems being
encountered with today’s growing networks. Effective routing algorithms use various techniques to determine
the most appropriate route for transmitting data. Determining the best route through a wide area network
(WAN), requires the routing algorithm to obtain information concerning all of the nodes, links, and devices
present on the network. The most relevant routing information involves various measures that are often
obtained in an imprecise or inaccurate manner, thus suggesting that fuzzy reasoning is a natural method to
employ in an improved routing scheme. The neural network is deemed as a suitable accompaniment because it
maintains the ability to learn in dynamic situations.

Once the neural network is initially designed, any alterations in the computer routing environment can
easily be learned by this adaptive artificial intelligence method. The capability to learn and adapt is
essential in today’s rapidly growing and changing computer networks. These techniques, fuzzy reasoning
and neural networks, when combined together provide a very effective routing algorithm for computer
networks. Computer simulation is employed to prove the new fuzzy routing algorithm outperforms the
Shortest Path First (SPF) algorithm in most computer network situations. The benefits increase as the
computer network migrates from a stable network to a more variable one. The advantages of applying this
fuzzy routing algorithm are apparent when considering the dynamic nature of modern computer networks.

Applying artificial intelligence to specific areas of network management allows the network engineer
to dedicate additional time and effort to the more specialized and intricate details of the system.
Many forms of artificial intelligence have previously been introduced to network management; however,
it appears that one of the more applicable areas, fuzzy reasoning, has been somewhat overlooked.
Computer network managers are often challenged with decision-making based on vague or partial
information. Similarly, computer networks frequently perform operational adjustments based on this
same vague or partial information. The imprecise nature of this information can lead to difficulties
and inaccuracies when automating network management using currently applied artificial intelligence
techniques. Fuzzy reasoning will allow this type of imprecise information to be dealt with in a
precise and well-defined manner, providing a more flawless method of automating the network
management decision making process.

The objective of this research is to explore the use of fuzzy reasoning in one area of network
management, namely the routing aspect of configuration management. A more effective method for
routing data through a computer network needs to be discovered to assist with the new problems
being encountered on today’s networks. Although traffic management is only one aspect of
configuration management, at this time it is one of the most visible networking issues. This
becomes apparent as consideration is given to the increasing number of network users and the
tremendous growth driven by Internet-based multimedia applications. Because of the number of
users and the distances between WAN users, efficient routing is more critical in wide area
networks than in LANs (also, many LAN architectures such as token ring do not allow any
flexibility in the nature of message passing). In order to determine the best route over the
WAN, it is necessary to obtain information concerning all of the nodes, links, and LANs present
in the wide area network. The most relevant routing information involves various measures
regarding each link. These measures include the distance a message will travel, bandwidth
available for transmitting that message (maximum signal frequency), packet size used to segment
the message (size of the data group being sent), and the likelihood of a link failure. These
are often measured in an imprecise or inaccurate manner, thus suggesting that fuzzy reasoning
is a natural method to employ in an improved routing scheme.

Utilizing fuzzy reasoning should assist in expressing these imprecise network measures; however, there
still remains the massive growth issue concerning traffic levels. Most routing algorithms currently
being implemented as a means of transmitting data from a source node to a destination node cannot
effectively handle this large traffic growth. Most network routing methods are designed to be efficient
for a current network situation; therefore, when the network deviates from the original situation, the
methods begin to lose efficiency. This suggests that an effective routing method should also be capable
of learning how to successfully adapt to network growth. Neural networks are extremely capable of
adapting to system changes, and thus will be applied as a second artificial intelligence technique to
the proposed routing method in this research. The proposed routing approach incorporates fuzzy reasoning
in order to prepare a more accurate assessment of the network’s traffic conditions, and hence provide a
faster, more reliable, or more efficient route for data exchange. Neural networks will be incorporated
into the routing method as a means for the routing method to adapt and learn how to successfully handle
network traffic growth. The combination of these two tools is expected to produce a more effective
routing method than is currently available.

In order to achieve the primary objective of more efficient routing, several minor objectives also need
to be accomplished. A method of data collection is needed throughout the different phases of the study.
Data collection will be accomplished through the use of simulation methods; therefore, a simulation model
must be accurately designed before proceeding with experimenting or analysis. Additional requirements
include building and training the neural network and defining the fuzzy system. The objective of this
research is to demonstrate the effective applicability of fuzzy reasoning to only one area of network
management, traffic routing.


, , , , , , , , , , , ,

1 Comment

Android Science, Toward a new cross-interdisciplinary framework

In the development of humanoids, both the appearance and behavior of the robots are significant issues.
However, designing the robot’s appearance, especially to give it a humanoid one, was always a role of the
industrial designer. To tackle the problem of appearance and behavior, two approaches are necessary: one
from robotics and the other from cognitive science. The approach from robotics tries to build very
humanlike robots based on knowledge from cognitive science. The approach from cognitive science uses the
robot for verifying hypotheses for understanding humans. We call this cross- interdisciplinary framework
android science. This conceptual paper introduces the developed androids and states the key issues in
android science.

Intelligence as subjective phenomena

How can we define intelligence ? This fundamental question motivates researchers in artificial intelligence
and robotics. Previous works in artificial intelligence considered functions of memory and prediction to
realize the intelligence of artificial systems. After the big wave of artificial intelligence in the 1980’s
and 1990’s, researchers focused on the importance of embodiment and started to use robots. The behavior-
based system proposed by Brooks was a trigger for this new wave. This means the main focus on artificial
intelligence and robotics has changed from an internal mechanism to interaction with the environment.
On the other hand, there are also two ideas in cognitive science. One is to focus on the internal
mechanism for understanding human intelligent behaviors, while the other focuses on the interactions
among people. This  approaches is studied in the framework of distributed cognition. The idea of
distributed cognition has similar aspects to the behavior-based system. The common concept is to
understand intelligence through human-human or human-robot interactions. This is also follows the ideas
of the behavior-based systems and distributed cognition. Because intelligence is a subjective phenomena,
it is therefore important to implement rich interactive behaviors with the robot. The author believes the
development of rich interactions among robots will provide hints of principles of communication systems,
with the design methodology of intelligent robots then being derived from those principles.

Constructive approach in robotics

First we have the question of how to develop the robots. There are explicit evaluation criteria for robot
navigation such as speed, precision, etc. On the other hand, our purpose is also to develop interactive
robots. If we have enough knowledge of humans, we may have explicit evaluation criteria. However this
knowledge is not sufficient to provide a top-down design; instead the potential approach is rather
bottom-up. By utilizing available sensors and actuators, we can design the behaviors of a robot and then
decide the execution rules among those behaviors. While doing this developing, we also evaluate the
robot’s performance and modify the behaviors and execution rules. This bottom-up approach is called the
constructive approach .In the constructive approach, interactions between a robot and a human are often
evaluated and analyzed through discussions with cognitive scientists and psychologists, with the robot
then being improved by the knowledge obtained through the discussions.

Appearance and behavior

In the evaluation, the performance measures are subjective impression of human subjects who interact with
the robot and their unconscious reactions, such as synchronized human behaviors in the interactions and eye
movements. Obviously, both the appearance and behavior of the robots are important factors in this
evaluation. There are many technical reports that compare robots with different behaviors. However nobody
has focused on appearance in the previous robotics. There many empirical discussions on very simplified
static robots, say dolls. Designing the robot’s appearance, especially to give it a humanoid one, was always
a role of the industrial designer. However we consider this to be a serious problem for developing and
evaluating interactive robots. Appearance and behavior are tightly coupled with both each other and these
problems, as the results of evaluation change with appearance. We developed several
humanoids for communicating with people, as shown in Figure 1. We empirically know the effect of appearance
is as significant as behaviors in communication. Human brain functions that recognize people support our
empirical knowledge.

Figure 1: From humanoids to androids. The first robot (the left end) is Robovie II developed by ATR
Intelligent Robotics and Communications Laboratories. The second is Wakamaru developed by Mitsubishi
Heavy Industry Co. Ltd. The third is a child android, while the fourth is the master of the child android.

Android Science

To tackle the problem of appearance and behavior, two approaches are necessary: one from robotics and the
other from cognitive science. The approach from robotics tries to build very humanlike robots based on
knowledge from cognitive science. The approach from cognitive science uses the robot for verifying hypotheses
for understanding humans. We call this cross-interdisciplinary framework android science.

Figure 2: The framework of android science

Previous robotics research also used knowledge of cognitive science while research in cognitive science
utilized robots. However the contribution from robotics to cognitive science was not enough as robot-like
robots were not sufficient as tools of cognitive science, because appearance and behavior cannot be separately
handled. We expect this problem to be solved by using an android that has an identical appearance to a human.
Robotics research utilizing hints from cognitive science also has a similar problem as it is difficult to
clearly recognize whether the hints are given for just robot behaviors isolated from their appearance or for
robots that have both the appearance and the behavior. In the framework of android science, androids enable us
to directly exchange knowledge between the development of androids in engineering and the understanding of
humans in cognitive science.

, , , , , , , , , ,

Leave a comment

Search Space Optimization

The optimizer considers each algebraic operation independently since the query decomposition step has
already taken global reorganization decisions. Optimization of all operations but the n-way Select
Project Join (SPJ) is quit straightforward. It consists of choosing the algorithm and the home of
operation. The crucial issue in terms of the search strategy is the join ordering problem, which
is NP-hard on the number of relations.

The search space, or solution space, is the set of all QEPs that compute the same result. A point
in the solution space is one particular plan, i. e. solution for the problem. A solution is
described by the query tree for executing the join expression. Every point of the search space
has a cost associated with it; a cost function maps query trees to their respective costs. The
query tree itself is a binary tree that consists of base relations as its leaves and joins
operations as its inner nodes; edges denote the flow of data that takes place from the leaves
of the tree to the root. As the join operation is commutative and associative, the number of
possible query trees increases quickly with increasing the number of relations involved in the
query. Thus, we reduce the goal of the query optimizer to find the best join order, together
with the best join method for each join. For a complex query, involving many relations and
many operators, the number of equivalent operator trees can be very high. Investigating a large
search space may make optimization time prohibitive, sometime much more expensive than the
execution time. Therefore, query optimizers typically restrict the size of the search space
they consider. The first restriction is to use heuristics. Another important restriction is the
shape of the join tree. The following sections discuss the characteristics of the most interesting
kinds of search spaces depending on the shape of the join tree they include.

Left-Deep and Right-Deep Trees

The search space restricted to only left-deep trees consists of all query trees where the inner
relation of each join is a base relation as in Figure 2-a. For a fixed number of base relations,
left-deep tree does not leave any degree of freedom concerning the shape of the tree, but there
are n! ways to allocate n base relations to the tree leaves.

Figure 2. Different query trees

In most sequential optimizers like the optimizer of IBM System R, the search space is restricted
to left-deep trees. The reason for this heuristic restriction is that the space including all trees
is much larger, while an optimal or nearly optimal plan can often be found in the much smaller
space of left-deep trees. When join algorithms are not symmetric, which is the case for hash-join,
it is useful to distinguish between left-deep and right-deep trees, see Figure 2-b. Hash-based join
algorithm have been shown to be the most efficient for equi-joins and particularly interesting in a
parallel environment because they naturally induce intra-operation parallelism. Hash-join usually
consists of two consecutive phases: Build and probe. In the build phase, a hash table is constructed
on the join attribute of the smallest relation. In the probe phase, the largest relation is
sequentially scanned and the hash table is consulted for each of its tuples.

, , , , , , , , , , , , , ,

Leave a comment

Shortest Path Algorithm for Multicast Routing in Multimedia Applications

A new heuristic algorithm is proposed for constructing multicast tree for multimedia and real-time applications.
The tree is used to concurrently transmit packets from source to multiple destinations such that exactly one
copy of any packet traverses the links of the multicast tree. Since multimedia applications require some
Quality of Service, QoS, a multicast tree is needed to satisfy two main goals, the minimum path cost
from source to each destination (Shortest Path Tree) and a certain end-to-end delay constraint from source to
each destination. This problem is known to be NP-Complete. The proposed heuristic algorithm solves this
problem in polynomial time and gives near optimal tree. We first mention some related work in this area then
we formalize the problem and introduce the new algorithm with its pseudo code and the proof of its complexity
and its correctness by showing that it always finds a feasible tree if one exists. Other heuristic algorithms
are examined and compared with the proposed algorithm via simulation.

Handling group communication is a key requirement for numerous applications that have one source sends
the same information concurrently to multiple destinations. Multicast routing refers to the construction
of a tree rooted at the source and spanning all destinations. Generally, there are two types of such a tree,
the Steiner tree and the shortest path tree. Steiner tree or group-shared tree tends to minimize the total
cost of the resulting tree, this is an NP-Complete problem. Shortest path tree or source-based trees tends
to minimize the cost of each path from source to any destination, this can be achieved in polynomial time
by using one of the two famous algorithms of Bellman and Dijkstra and pruning the undesired links. Recently,
with the rapid evolution of multimedia and real-time applications like audio/video conferencing, interactive
distributed games and real-time remote control system, certain QoS need to be guaranteed in the resulted
tree. One such QoS, and the most important one is the end-to-end delay between source and each destination,
where the information must be sent within a certain delay constraint D. By adding this constraint to the
original problem of multicast routing, the problem is reformulated and the multicast tree should be either
delay constrained Steiner tree, or delay-constrained shortest path tree. Delay constrained Steiner tree
is an NP-Complete problem, several heuristics are introduced for this problem each trying to get near
optimal tree cost, without regarding to the cost of each individual path for each destination. Delay
constrained shortest path tree is also an NP-Complete problem. An optimal algorithm for this problem
is presented, but its execution time is exponential and used only for comparison with other algorithms.
Heuristic for this problem is presented, which tries to get a near optimal tree from the point of
view of each destination without regarding the total cost of the tree. An exhaustive comparison between
the previous heuristics for the two problems can be found. We investigate the problem of delay
constrained shortest path tree since it is appropriate in some applications like Video on Demand (VoD),
where the multicast group has a frequent change, and every user wants to get his information in the lowest
possible cost for him without regarding the total cost of the routing tree. Also shortest path tree always
gives average cost per destination less than Steiner tree. We present a new heuristic algorithm that finds
the required tree in polynomial time.

, , , , , , , , , , , , , ,

Leave a comment

FPGA Based Dijkstra’s Shortest Path Algorithm

A parameterizable version of Dijkstra’s shortest path algorithm was designed in VHDL with Synopsys’ FPGA
Express design software version 3.4. The design was targeted for Altera’s FLEX10K device family with the
Quartus design software. The parameterizable features of Dijkstra’s shortest path algorithm were compiled
into a separate VHDL package which was included in the main design file. This way the design of other
versions of Dijsktra’s algorithm with different accuracy and for networks of different sizes is made
easier, since all the changes are made only in the VHDL package.

Fig. 1. The top-level block diagram of the FPGA-based Dijkstra’s shortest path algorithm. The ROM block
contains the network description and the RAM block contains the temporary results of shortest path
computation. The comparator bank selects the smallest distance from the prefetched edge lengths.

The block diagram of the FPGA-based Dijkstra’s shortest path algorithm is presented in Fig. 1. The
network structure is presented in the internal ROM block of the logic device. In the block diagram
of Fig. 1, there are six address lines. This is sufficient to represent all node-to-node links of
networks of size upto eight nodes, if the network is represented as an adjacency matrix. The
internal RAM blocks of the logic device represent the known status of nodes, the distance to this
node and the previous node. There are separate address and data lines for the ROM and RAM blocks,
which allows the parallel transfer of information to/from the memory blocks. To speed up the
computations for finding the closest node from the set of unknown nodes, all node-to-node links
whose other pair is the last known node are prefetched from ROM. Then the next known node is
computed by the parallel comparator bank.

As an example, the compiled version of Dijsktra’s algorithm for networks of maximum sixe eight nodes
fitted into an EPF10K20TC144-3 device, which has 1152 logic elements (LEs) corresponding to
approximately 20000 available gates. The design required 72 per cent of all LEs and 5 per cent of
available memory bits. Logic element requirements increase linearly, since the size of the comparator
bank grows linearly. On the other hand, memory requirements increase quadratically,since the network
description of a network of size N nodes requires NxN memory locations. If the network description
requires an external memory chip, all that is needed is to add an external data and address bus and
to change the memory handling functions to handle external memory instead of internal memory.

To compare the performance of an FPGA-based Dijsktra’s algorithm with a microprocessor-based version,
an identical algorithm was coded in C and compiled with gcc in Linux Redhat 6.2. The same network
descriptions were then tried in both the FPGA-based and software-based versions of the same algorithm.
The speedup factor in favor of the FPGA-based version depended on the number of network nodes. As
network sizes grew, the average execution time of the FPGA-based version grew only linearly, whereas
the average execution time of the microprocessor-based version displayed quadratic growth
(in Table 2). This can be attributed to the more effective FPGA-based execution in Dijkstra’s
algorithm, since multiple comparators are used in parallel.

Table 2. FPGA resources required by the implementation of Dijkstra’s shortest path algorithm and a
comparison between the execution times of FPGA-based and microprocessor-based versions of the same algorithm.

, , , , , , , , , , , , ,

Leave a comment

%d bloggers like this: